[problem:1420A]↵
↵
<spoiler summary="Подсказка">↵
Любой массив можно отсортировать не более, чем за $\frac{n(n-1)}2$ операций. Подумайте либо угадайте, в каком случае понадобится ровноHint">↵
Any array can be sorted using no more than $\frac{n(n-1)}2$ operations. Think or guess when we need exactly $\frac{n(n-1)}2$ operations.↵
</spoiler>↵
↵
<spoiler summary="РазборSolution">↵
[tutorial:1420A]↵
</spoiler>↵
↵
<spoiler summary="КодCode in C++ (Wind_Eagle)">↵
~~~~~↵
#include<iostream>↵
↵
using namespace std;↵
↵
int a[1000000+5];↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin>>t;↵
while (t--)↵
{↵
int n;↵
cin>>n;↵
for (int i=0; i<n; i++)↵
{↵
cin>>a[i];↵
}↵
bool can=false;↵
for (int i=1; i<n; i++)↵
{↵
if (a[i]>=a[i-1])↵
{↵
can=true;↵
break;↵
}↵
}↵
if (can) cout<<"YES"<<'\n';↵
else cout<<"NO"<<'\n';↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1420B]↵
↵
<spoiler summary="Подсказка">↵
Придумайте простой критерий, когда `a_i & a_j >= a_i ^ a_j$, рассмотрев биты от старшего к младшему. Примените его, чтобы быстро вычислить ответHint">↵
Think of a simple criteria when `a_i & a_j >= a_i ^ a_j` by considering the bits from highest to lowest. Apply your observations to calculate the answer fast.↵
</spoiler>↵
↵
<spoiler summary="РазборSolution">↵
[tutorial:1420B]↵
</spoiler>↵
↵
<spoiler summary="КодCode in C++ (Wind_Eagle)">↵
~~~~~↵
#include<iostream>↵
#include<vector>↵
#include<algorithm>↵
#include<ctime>↵
#include<random>↵
↵
using namespace std;↵
↵
mt19937 rnd(time(NULL));↵
↵
int a[1000000+5];↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin>>t;↵
while (t--)↵
{↵
int n;↵
cin>>n;↵
for (int i=0; i<n; i++)↵
{↵
cin>>a[i];↵
}↵
int64_t ans=0;↵
for (int j=29; j>=0; j--)↵
{↵
int64_t cnt=0;↵
for (int i=0; i<n; i++)↵
{↵
if (a[i]>=(1<<j)&&a[i]<(1<<(j+1)))↵
{↵
cnt++;↵
}↵
}↵
ans+=cnt*(cnt-1)/2;↵
}↵
cout<<ans<<'\n';↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1420C1]↵
↵
<spoiler summary="Подсказка">↵
Используйте динамическое программированиеHint">↵
Use dynamic programming.↵
</spoiler>↵
↵
<spoiler summary="РазборSolution">↵
[tutorial:1420C1]↵
</spoiler>↵
↵
<spoiler summary="КодCode in C++ (gepardo)">↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
↵
using namespace std;↵
↵
inline int64_t calc(const vector<int> &a) {↵
int n = a.size();↵
vector<int64_t> d1(n+1), d2(n+1);↵
d1[0] = -static_cast<int64_t>(1e18);↵
d2[0] = 0;↵
for (int i = 0; i < n; ++i) {↵
d1[i+1] = max(d1[i], d2[i] + a[i]);↵
d2[i+1] = max(d2[i], d1[i] - a[i]);↵
}↵
return max(d1.back(), d2.back());↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
int t; cin >> t;↵
while (t--) {↵
int n, q; cin >> n >> q;↵
vector<int> a(n);↵
for (int i = 0; i < n; ++i) {↵
cin >> a[i];↵
}↵
cout << calc(a) << "\n";↵
for (int i = 0; i < q; ++i) {↵
int l, r; cin >> l >> r; --l; --r;↵
swap(a[l], a[r]);↵
cout << calc(a) << "\n";↵
}↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1420C2]↵
↵
<spoiler summary="Подсказка">↵
Здесь динамическое программирование не сработает. Подумайте, выгодно ли брать в ответ что-либо, кроме локальных минимумов и максимумовHint">↵
The dynamic programming doesn't work here. Consider taking only local minima and maxima and think whether we need to take something else.↵
</spoiler>↵
↵
<spoiler summary="РазборSolution">↵
[tutorial:1420C2]↵
</spoiler>↵
↵
<spoiler summary="КодCode in Java (gepardo)">↵
~~~~~↵
import java.io.*;↵
import java.util.*;↵
↵
public class C2_Java {↵
int[] a;↵
int n;↵
long ans;↵
↵
void add(int i, int sign) {↵
if (i == 0 || i == n+1) return;↵
if (a[i-1] < a[i] && a[i] > a[i+1]) ans += sign * a[i];↵
if (a[i-1] > a[i] && a[i] < a[i+1]) ans -= sign * a[i];↵
}↵
↵
void addTwo(int l, int r, int sign) {↵
if (l == r) return;↵
if (l+1 == r) {↵
add(l-1, sign);↵
add(l, sign);↵
add(r, sign);↵
add(r+1, sign);↵
return;↵
}↵
add(l-1, sign);↵
add(l, sign);↵
add(l+1, sign);↵
if (l+2 != r) add(r-1, sign);↵
add(r, sign);↵
add(r+1, sign);↵
}↵
↵
public void run() throws IOException {↵
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));↵
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));↵
↵
StringTokenizer tok = new StringTokenizer(in.readLine());↵
int t = Integer.parseInt(tok.nextToken());↵
while (t --> 0) {↵
tok = new StringTokenizer(in.readLine());↵
n = Integer.parseInt(tok.nextToken());↵
int q = Integer.parseInt(tok.nextToken());↵
a = new int[n + 2];↵
tok = new StringTokenizer(in.readLine());↵
for (int i = 1; i <= n; ++i) {↵
a[i] = Integer.parseInt(tok.nextToken());↵
}↵
a[0] = -1;↵
a[n+1] = -1;↵
ans = 0;↵
StringBuilder builder = new StringBuilder();↵
for (int i = 1; i <= n; ++i) {↵
if (a[i-1] < a[i] && a[i] > a[i+1]) ans += a[i];↵
if (a[i-1] > a[i] && a[i] < a[i+1]) ans -= a[i];↵
}↵
builder.append(ans).append("\n");↵
while (q --> 0) {↵
tok = new StringTokenizer(in.readLine());↵
int l = Integer.parseInt(tok.nextToken());↵
int r = Integer.parseInt(tok.nextToken());↵
if (l == r) {↵
builder.append(ans).append("\n");↵
continue;↵
}↵
addTwo(l, r, -1);↵
int tmp = a[l];↵
a[l] = a[r];↵
a[r] = tmp;↵
addTwo(l, r, +1);↵
builder.append(ans).append("\n");↵
}↵
out.write(builder.toString()); ↵
}↵
↵
in.close();↵
out.close(); ↵
}↵
↵
public static void main(String[] args) throws IOException {↵
(new C2_Java()).run();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="КодCode in C++ (Wind_Eagle)">↵
~~~~~↵
#include<iostream>↵
↵
using namespace std;↵
↵
#define int long long↵
↵
int a[1000000+5];↵
↵
int n;↵
↵
int ans=0;↵
↵
inline void insert(int i)↵
{↵
if (i==0||i==n+1) return;↵
if (a[i-1]<a[i]&&a[i]>a[i+1]) ans+=a[i];↵
if (a[i-1]>a[i]&&a[i]<a[i+1]) ans-=a[i];↵
}↵
↵
inline void erase(int i)↵
{↵
if (i==0||i==n+1) return;↵
if (a[i-1]<a[i]&&a[i]>a[i+1]) ans-=a[i];↵
if (a[i-1]>a[i]&&a[i]<a[i+1]) ans+=a[i];↵
}↵
↵
int32_t main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin>>t;↵
while (t--)↵
{↵
int q;↵
cin>>n>>q;↵
for (int i=1; i<=n; i++)↵
{↵
cin>>a[i];↵
}↵
a[0]=-1;↵
a[n+1]=-1;↵
ans=0;↵
for (int i=1; i<=n; i++)↵
{↵
if (a[i-1]<a[i]&&a[i]>a[i+1]) ans+=a[i];↵
if (a[i-1]>a[i]&&a[i]<a[i+1]) ans-=a[i];↵
}↵
cout<<ans<<'\n';↵
while (q--)↵
{↵
int l,r;↵
cin>>l>>r;↵
erase(l-1);↵
erase(l);↵
erase(l+1);↵
if (l!=r)↵
{↵
if (r-1!=l+1&&r-1!=l) erase(r-1);↵
if (r!=l+1) erase(r);↵
erase(r+1);↵
}↵
swap(a[l],a[r]);↵
insert(l-1);↵
insert(l);↵
insert(l+1);↵
if (l!=r)↵
{↵
if (r-1!=l+1&&r-1!=l) insert(r-1);↵
if (r!=l+1) insert(r);↵
insert(r+1);↵
}↵
cout<<ans<<'\n';↵
}↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1420D]↵
↵
<spoiler summary="Подсказка">↵
Пересечение любых $k$ отрезков либо пусто, либо дает отрезок. Зафиксируйте левую границу пересечения и посчитайте количество наборов из $k$ отрезков, у которых пересечение начинается в этой левой границеHint">↵
The intersection of any $k$ segments is either empty or is a segment. Let's fix the left bound of the intersection and calculate the number of sets of $k$ segments such that their intersection starts in this left bound.↵
</spoiler>↵
↵
<spoiler summary="РазборSolution">↵
[tutorial:1420D]↵
</spoiler>↵
↵
<spoiler summary="КодCode in Java (gepardo)">↵
~~~~~↵
import java.io.*;↵
import java.util.*;↵
↵
public class D_Java {↵
public static final int MOD = 998244353;↵
↵
public static int mul(int a, int b) {↵
return (int)((long)a * (long)b % MOD);↵
}↵
↵
int[] f;↵
int[] rf;↵
↵
public int C(int n, int k) {↵
return (k < 0 || k > n) ? 0 : mul(f[n], mul(rf[n-k], rf[k]));↵
}↵
↵
public static int pow(int a, int n) {↵
int res = 1;↵
while (n != 0) {↵
if ((n & 1) == 1) {↵
res = mul(res, a);↵
}↵
a = mul(a, a);↵
n >>= 1;↵
}↵
return res;↵
}↵
↵
static void shuffleArray(int[] a) {↵
Random rnd = new Random();↵
for (int i = a.length-1; i > 0; i--) {↵
int index = rnd.nextInt(i + 1);↵
int tmp = a[index];↵
a[index] = a[i];↵
a[i] = tmp;↵
}↵
}↵
↵
public static int inv(int a) {↵
return pow(a, MOD-2);↵
}↵
↵
public void doIt() throws IOException {↵
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));↵
↵
StringTokenizer tok = new StringTokenizer(in.readLine());↵
int n = Integer.parseInt(tok.nextToken());↵
int k = Integer.parseInt(tok.nextToken());↵
↵
f = new int[n+42];↵
rf = new int[n+42];↵
f[0] = rf[0] = 1;↵
for (int i = 1; i < f.length; ++i) {↵
f[i] = mul(f[i-1], i);↵
rf[i] = mul(rf[i-1], inv(i));↵
}↵
↵
int[] events = new int[2*n];↵
for (int i = 0; i < n; ++i) {↵
tok = new StringTokenizer(in.readLine());↵
int le = Integer.parseInt(tok.nextToken());↵
int ri = Integer.parseInt(tok.nextToken());↵
events[i] = le*2;↵
events[i + n] = ri*2 + 1;↵
}↵
shuffleArray(events);↵
Arrays.sort(events);↵
↵
int ans = 0;↵
int balance = 0;↵
for (int r = 0; r < 2*n;) {↵
int l = r;↵
while (r < 2*n && events[l] == events[r]) {↵
++r;↵
}↵
int added = r - l;↵
if (events[l] % 2 == 0) {↵
// Open event↵
ans += C(balance + added, k);↵
if (ans >= MOD) ans -= MOD;↵
ans += MOD - C(balance, k);↵
if (ans >= MOD) ans -= MOD;↵
balance += added;↵
} else {↵
// Close event↵
balance -= added;↵
}↵
}↵
↵
in.close();↵
System.out.println(ans);↵
}↵
↵
public static void main(String[] args) throws IOException {↵
(new D_Java()).doIt();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1420E]↵
↵
<spoiler summary="Подсказка 1">↵
Давайте вместо массива из нулей и единиц будем хранить количество нулей между каждой парой соседних единиц. Как тогда будут выглядеть операции обмена? А как посчитать защищенность армии в таком случае?↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Пусть нам дан исходный массив и конечный. Подумайте, за сколько операций можно первый превратить во второй.↵
</spoiler>↵
↵
<spoiler summary="Подсказка 3">↵
Соедините все вместе и напишите ДПHint 1">↵
Let's keep the number of zeroes between any pair consecutive ones instead of the original array of zeroes and ones. How will the swap operation look in this case. How to calculate the protection?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Suppose we have the initial array and the final array. Think of the number of operations you need to make the first one equal to the second one.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Join all your observations together and use DP.↵
</spoiler>↵
↵
<spoiler summary="РазборSolution">↵
[tutorial:1420E]↵
</spoiler>↵
↵
<spoiler summary="КодCode in C++ (gepardo)">↵
~~~~~↵
#include <cassert>↵
#include <climits>↵
#include <iostream>↵
#include <vector>↵
#include <numeric>↵
↵
using namespace std;↵
↵
template<typename T>↵
inline void umin(T &a, const T &b) {↵
a = min(a, b);↵
}↵
↵
template<typename T>↵
inline void umax(T &a, const T &b) {↵
a = max(a, b);↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
↵
int n; cin >> n;↵
vector<int> a(n);↵
for (int &x : a) {↵
cin >> x;↵
}↵
a.push_back(1);↵
↵
vector<int> gg;↵
for (int i = 0; i <= n; ++i) {↵
int s = i;↵
while (a[i] == 0) ++i;↵
gg.push_back(i - s);↵
}↵
↵
vector<int> p = gg;↵
partial_sum(begin(p), end(p), begin(p));↵
↵
constexpr int mx = 103;↵
constexpr int dx = mx + 1, dy = mx + 1, dz = mx * (mx + 1) / 2 + 1;↵
static int dp[dx][dy][dz] = {};↵
↵
for (int i = 0; i < dx; ++i) {↵
for (int j = 0; j < dy; ++j) {↵
for (int k = 0; k < dz; ++k) {↵
dp[i][j][k] = INT_MAX;↵
}↵
}↵
}↵
dp[0][0][0] = 0;↵
↵
int k = gg.size(), l = p.back();↵
for (int i = 0; i < k; ++i) {↵
for (int j = 0; j <= l; ++j) {↵
for (int s = 0; s <= n * (n-1) / 2; ++s) {↵
if (dp[i][j][s] == INT_MAX) continue;↵
for (int q = j; q <= l; ++q) {↵
umin(dp[i+1][q][s + abs(q - p[i])], dp[i][j][s] + (q-j)*(q-j));↵
}↵
}↵
}↵
}↵
↵
int mn = INT_MAX;↵
for (int s = 0; s <= n * (n-1) / 2; ++s) {↵
umin(mn, dp[k][l][s]);↵
int val = l*l - mn;↵
assert(val % 2 == 0);↵
cout << val/2 << " ";↵
}↵
cout << endl;↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
<spoiler summary="
Любой массив можно отсортировать не более, чем за $\frac{n(n-1)}2$ операций. Подумайте либо угадайте, в каком случае понадобится ровно
Any array can be sorted using no more than $\frac{n(n-1)}2$ operations. Think or guess when we need exactly $\frac{n(n-1)}2$ operations.↵
</spoiler>↵
↵
<spoiler summary="
[tutorial:1420A]↵
</spoiler>↵
↵
<spoiler summary="
~~~~~↵
#include<iostream>↵
↵
using namespace std;↵
↵
int a[1000000+5];↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin>>t;↵
while (t--)↵
{↵
int n;↵
cin>>n;↵
for (int i=0; i<n; i++)↵
{↵
cin>>a[i];↵
}↵
bool can=false;↵
for (int i=1; i<n; i++)↵
{↵
if (a[i]>=a[i-1])↵
{↵
can=true;↵
break;↵
}↵
}↵
if (can) cout<<"YES"<<'\n';↵
else cout<<"NO"<<'\n';↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1420B]↵
↵
<spoiler summary="
Придумайте простой критерий, когда `a_i & a_j >= a_i ^ a_j$, рассмотрев биты от старшего к младшему. Примените его, чтобы быстро вычислить ответ
Think of a simple criteria when `a_i & a_j >= a_i ^ a_j` by considering the bits from highest to lowest. Apply your observations to calculate the answer fast.↵
</spoiler>↵
↵
<spoiler summary="
[tutorial:1420B]↵
</spoiler>↵
↵
<spoiler summary="
~~~~~↵
#include<iostream>↵
#include<vector>↵
#include<algorithm>↵
#include<ctime>↵
#include<random>↵
↵
using namespace std;↵
↵
mt19937 rnd(time(NULL));↵
↵
int a[1000000+5];↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin>>t;↵
while (t--)↵
{↵
int n;↵
cin>>n;↵
for (int i=0; i<n; i++)↵
{↵
cin>>a[i];↵
}↵
int64_t ans=0;↵
for (int j=29; j>=0; j--)↵
{↵
int64_t cnt=0;↵
for (int i=0; i<n; i++)↵
{↵
if (a[i]>=(1<<j)&&a[i]<(1<<(j+1)))↵
{↵
cnt++;↵
}↵
}↵
ans+=cnt*(cnt-1)/2;↵
}↵
cout<<ans<<'\n';↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1420C1]↵
↵
<spoiler summary="
Используйте динамическое программирование
Use dynamic programming.↵
</spoiler>↵
↵
<spoiler summary="
[tutorial:1420C1]↵
</spoiler>↵
↵
<spoiler summary="
~~~~~↵
#include <iostream>↵
#include <vector>↵
↵
using namespace std;↵
↵
inline int64_t calc(const vector<int> &a) {↵
int n = a.size();↵
vector<int64_t> d1(n+1), d2(n+1);↵
d1[0] = -static_cast<int64_t>(1e18);↵
d2[0] = 0;↵
for (int i = 0; i < n; ++i) {↵
d1[i+1] = max(d1[i], d2[i] + a[i]);↵
d2[i+1] = max(d2[i], d1[i] - a[i]);↵
}↵
return max(d1.back(), d2.back());↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
int t; cin >> t;↵
while (t--) {↵
int n, q; cin >> n >> q;↵
vector<int> a(n);↵
for (int i = 0; i < n; ++i) {↵
cin >> a[i];↵
}↵
cout << calc(a) << "\n";↵
for (int i = 0; i < q; ++i) {↵
int l, r; cin >> l >> r; --l; --r;↵
swap(a[l], a[r]);↵
cout << calc(a) << "\n";↵
}↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1420C2]↵
↵
<spoiler summary="
Здесь динамическое программирование не сработает. Подумайте, выгодно ли брать в ответ что-либо, кроме локальных минимумов и максимумов
The dynamic programming doesn't work here. Consider taking only local minima and maxima and think whether we need to take something else.↵
</spoiler>↵
↵
<spoiler summary="
[tutorial:1420C2]↵
</spoiler>↵
↵
<spoiler summary="
~~~~~↵
import java.io.*;↵
import java.util.*;↵
↵
public class C2_Java {↵
int[] a;↵
int n;↵
long ans;↵
↵
void add(int i, int sign) {↵
if (i == 0 || i == n+1) return;↵
if (a[i-1] < a[i] && a[i] > a[i+1]) ans += sign * a[i];↵
if (a[i-1] > a[i] && a[i] < a[i+1]) ans -= sign * a[i];↵
}↵
↵
void addTwo(int l, int r, int sign) {↵
if (l == r) return;↵
if (l+1 == r) {↵
add(l-1, sign);↵
add(l, sign);↵
add(r, sign);↵
add(r+1, sign);↵
return;↵
}↵
add(l-1, sign);↵
add(l, sign);↵
add(l+1, sign);↵
if (l+2 != r) add(r-1, sign);↵
add(r, sign);↵
add(r+1, sign);↵
}↵
↵
public void run() throws IOException {↵
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));↵
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));↵
↵
StringTokenizer tok = new StringTokenizer(in.readLine());↵
int t = Integer.parseInt(tok.nextToken());↵
while (t --> 0) {↵
tok = new StringTokenizer(in.readLine());↵
n = Integer.parseInt(tok.nextToken());↵
int q = Integer.parseInt(tok.nextToken());↵
a = new int[n + 2];↵
tok = new StringTokenizer(in.readLine());↵
for (int i = 1; i <= n; ++i) {↵
a[i] = Integer.parseInt(tok.nextToken());↵
}↵
a[0] = -1;↵
a[n+1] = -1;↵
ans = 0;↵
StringBuilder builder = new StringBuilder();↵
for (int i = 1; i <= n; ++i) {↵
if (a[i-1] < a[i] && a[i] > a[i+1]) ans += a[i];↵
if (a[i-1] > a[i] && a[i] < a[i+1]) ans -= a[i];↵
}↵
builder.append(ans).append("\n");↵
while (q --> 0) {↵
tok = new StringTokenizer(in.readLine());↵
int l = Integer.parseInt(tok.nextToken());↵
int r = Integer.parseInt(tok.nextToken());↵
if (l == r) {↵
builder.append(ans).append("\n");↵
continue;↵
}↵
addTwo(l, r, -1);↵
int tmp = a[l];↵
a[l] = a[r];↵
a[r] = tmp;↵
addTwo(l, r, +1);↵
builder.append(ans).append("\n");↵
}↵
out.write(builder.toString()); ↵
}↵
↵
in.close();↵
out.close(); ↵
}↵
↵
public static void main(String[] args) throws IOException {↵
(new C2_Java()).run();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
~~~~~↵
#include<iostream>↵
↵
using namespace std;↵
↵
#define int long long↵
↵
int a[1000000+5];↵
↵
int n;↵
↵
int ans=0;↵
↵
inline void insert(int i)↵
{↵
if (i==0||i==n+1) return;↵
if (a[i-1]<a[i]&&a[i]>a[i+1]) ans+=a[i];↵
if (a[i-1]>a[i]&&a[i]<a[i+1]) ans-=a[i];↵
}↵
↵
inline void erase(int i)↵
{↵
if (i==0||i==n+1) return;↵
if (a[i-1]<a[i]&&a[i]>a[i+1]) ans-=a[i];↵
if (a[i-1]>a[i]&&a[i]<a[i+1]) ans+=a[i];↵
}↵
↵
int32_t main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin>>t;↵
while (t--)↵
{↵
int q;↵
cin>>n>>q;↵
for (int i=1; i<=n; i++)↵
{↵
cin>>a[i];↵
}↵
a[0]=-1;↵
a[n+1]=-1;↵
ans=0;↵
for (int i=1; i<=n; i++)↵
{↵
if (a[i-1]<a[i]&&a[i]>a[i+1]) ans+=a[i];↵
if (a[i-1]>a[i]&&a[i]<a[i+1]) ans-=a[i];↵
}↵
cout<<ans<<'\n';↵
while (q--)↵
{↵
int l,r;↵
cin>>l>>r;↵
erase(l-1);↵
erase(l);↵
erase(l+1);↵
if (l!=r)↵
{↵
if (r-1!=l+1&&r-1!=l) erase(r-1);↵
if (r!=l+1) erase(r);↵
erase(r+1);↵
}↵
swap(a[l],a[r]);↵
insert(l-1);↵
insert(l);↵
insert(l+1);↵
if (l!=r)↵
{↵
if (r-1!=l+1&&r-1!=l) insert(r-1);↵
if (r!=l+1) insert(r);↵
insert(r+1);↵
}↵
cout<<ans<<'\n';↵
}↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1420D]↵
↵
<spoiler summary="
Пересечение любых $k$ отрезков либо пусто, либо дает отрезок. Зафиксируйте левую границу пересечения и посчитайте количество наборов из $k$ отрезков, у которых пересечение начинается в этой левой границе
The intersection of any $k$ segments is either empty or is a segment. Let's fix the left bound of the intersection and calculate the number of sets of $k$ segments such that their intersection starts in this left bound.↵
</spoiler>↵
↵
<spoiler summary="
[tutorial:1420D]↵
</spoiler>↵
↵
<spoiler summary="
~~~~~↵
import java.io.*;↵
import java.util.*;↵
↵
public class D_Java {↵
public static final int MOD = 998244353;↵
↵
public static int mul(int a, int b) {↵
return (int)((long)a * (long)b % MOD);↵
}↵
↵
int[] f;↵
int[] rf;↵
↵
public int C(int n, int k) {↵
return (k < 0 || k > n) ? 0 : mul(f[n], mul(rf[n-k], rf[k]));↵
}↵
↵
public static int pow(int a, int n) {↵
int res = 1;↵
while (n != 0) {↵
if ((n & 1) == 1) {↵
res = mul(res, a);↵
}↵
a = mul(a, a);↵
n >>= 1;↵
}↵
return res;↵
}↵
↵
static void shuffleArray(int[] a) {↵
Random rnd = new Random();↵
for (int i = a.length-1; i > 0; i--) {↵
int index = rnd.nextInt(i + 1);↵
int tmp = a[index];↵
a[index] = a[i];↵
a[i] = tmp;↵
}↵
}↵
↵
public static int inv(int a) {↵
return pow(a, MOD-2);↵
}↵
↵
public void doIt() throws IOException {↵
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));↵
↵
StringTokenizer tok = new StringTokenizer(in.readLine());↵
int n = Integer.parseInt(tok.nextToken());↵
int k = Integer.parseInt(tok.nextToken());↵
↵
f = new int[n+42];↵
rf = new int[n+42];↵
f[0] = rf[0] = 1;↵
for (int i = 1; i < f.length; ++i) {↵
f[i] = mul(f[i-1], i);↵
rf[i] = mul(rf[i-1], inv(i));↵
}↵
↵
int[] events = new int[2*n];↵
for (int i = 0; i < n; ++i) {↵
tok = new StringTokenizer(in.readLine());↵
int le = Integer.parseInt(tok.nextToken());↵
int ri = Integer.parseInt(tok.nextToken());↵
events[i] = le*2;↵
events[i + n] = ri*2 + 1;↵
}↵
shuffleArray(events);↵
Arrays.sort(events);↵
↵
int ans = 0;↵
int balance = 0;↵
for (int r = 0; r < 2*n;) {↵
int l = r;↵
while (r < 2*n && events[l] == events[r]) {↵
++r;↵
}↵
int added = r - l;↵
if (events[l] % 2 == 0) {↵
// Open event↵
ans += C(balance + added, k);↵
if (ans >= MOD) ans -= MOD;↵
ans += MOD - C(balance, k);↵
if (ans >= MOD) ans -= MOD;↵
balance += added;↵
} else {↵
// Close event↵
balance -= added;↵
}↵
}↵
↵
in.close();↵
System.out.println(ans);↵
}↵
↵
public static void main(String[] args) throws IOException {↵
(new D_Java()).doIt();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:1420E]↵
↵
<spoiler summary="
Давайте вместо массива из нулей и единиц будем хранить количество нулей между каждой парой соседних единиц. Как тогда будут выглядеть операции обмена? А как посчитать защищенность армии в таком случае?↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Пусть нам дан исходный массив и конечный. Подумайте, за сколько операций можно первый превратить во второй.↵
</spoiler>↵
↵
<spoiler summary="Подсказка 3">↵
Соедините все вместе и напишите ДП
Let's keep the number of zeroes between any pair consecutive ones instead of the original array of zeroes and ones. How will the swap operation look in this case. How to calculate the protection?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Suppose we have the initial array and the final array. Think of the number of operations you need to make the first one equal to the second one.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Join all your observations together and use DP.↵
</spoiler>↵
↵
<spoiler summary="
[tutorial:1420E]↵
</spoiler>↵
↵
<spoiler summary="
~~~~~↵
#include <cassert>↵
#include <climits>↵
#include <iostream>↵
#include <vector>↵
#include <numeric>↵
↵
using namespace std;↵
↵
template<typename T>↵
inline void umin(T &a, const T &b) {↵
a = min(a, b);↵
}↵
↵
template<typename T>↵
inline void umax(T &a, const T &b) {↵
a = max(a, b);↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
↵
int n; cin >> n;↵
vector<int> a(n);↵
for (int &x : a) {↵
cin >> x;↵
}↵
a.push_back(1);↵
↵
vector<int> gg;↵
for (int i = 0; i <= n; ++i) {↵
int s = i;↵
while (a[i] == 0) ++i;↵
gg.push_back(i - s);↵
}↵
↵
vector<int> p = gg;↵
partial_sum(begin(p), end(p), begin(p));↵
↵
constexpr int mx = 103;↵
constexpr int dx = mx + 1, dy = mx + 1, dz = mx * (mx + 1) / 2 + 1;↵
static int dp[dx][dy][dz] = {};↵
↵
for (int i = 0; i < dx; ++i) {↵
for (int j = 0; j < dy; ++j) {↵
for (int k = 0; k < dz; ++k) {↵
dp[i][j][k] = INT_MAX;↵
}↵
}↵
}↵
dp[0][0][0] = 0;↵
↵
int k = gg.size(), l = p.back();↵
for (int i = 0; i < k; ++i) {↵
for (int j = 0; j <= l; ++j) {↵
for (int s = 0; s <= n * (n-1) / 2; ++s) {↵
if (dp[i][j][s] == INT_MAX) continue;↵
for (int q = j; q <= l; ++q) {↵
umin(dp[i+1][q][s + abs(q - p[i])], dp[i][j][s] + (q-j)*(q-j));↵
}↵
}↵
}↵
}↵
↵
int mn = INT_MAX;↵
for (int s = 0; s <= n * (n-1) / 2; ++s) {↵
umin(mn, dp[k][l][s]);↵
int val = l*l - mn;↵
assert(val % 2 == 0);↵
cout << val/2 << " ";↵
}↵
cout << endl;↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
