Codeforces Round 873 (Div. 2) A~D2
A. Divisible Array
因为\(1\)一定整除，构造\(a_i=i\)，再让\(a_1\)加上和模\(n\)的余数
void work() {
int n;
cin >> n;
vector<int> a(n + 1);
int s = 0;
rep (i, 1, n) a[i] = i, s += i;
a[1] += s % n;
rep (i, 1, n) cout << a[i] << " \n"[i == n];
}
B. Permutation Swap
对于\(p_i\)肯定要移动到位置\(i\)，那么移动的步数一定能整除\(abs(p_i-i)\)
void work() {
int n;
cin >> n;
vector<int> a(n + 1), b(n + 1);
rep (i, 1, n) cin >> a[i], b[a[i]] = i;
int res = 0;
rep (i, 1, n) res = __gcd(res, abs(b[i] - i));
cout << res << "\n";
}
C. Counting Orders
排序不影响答案统计，从大到小排序后，第\(i\)个位置能选择的数一定是第\(i+1\)个位置能选的子集
void work() {
int n;
cin >> n;
vector<int> a(n + 1), b(n + 1), s(n + 1);
rep (i, 1, n) cin >> a[i];
rep (i, 1, n) cin >> b[i];
sort(a.begin() + 1, a.end());
sort(b.begin() + 1, b.end());
int pos = 1;
rep (i, 1, n) {
while (pos <= n && a[pos] <= b[i]) pos++;
s[i] = n - pos + 1;
}
int res = 1;
rrep (i, n, 1) {
int p = max(0, s[i] - (n - i));
res = 1ll * res * p % MOD;
}
cout << res << "\n";
}
D1. Range Sorting (Easy Version)
选择的两两区间一定不相交，如果相交用它们的并区间替换它们只会使答案更优。
第\(i\)个数加入后贡献了\(i\)个区间，对于区间\([l, i](1 \le l\le i)\)，最终排序后\(a_i\)的位置为\(k\)，那么\([k, i]\)这个区间一定是要被包含的，试想能否单独考虑\([l,k-1]\)这个区间，如果可以就能用\(dp\)转移了，可以发现只有当\(max(a_l,a_{l+1},...,a_{k-1})<min(a_k,a_{k+1},...,a_i)\)时才成立，所以我们在扩大区间时顺便维护最大的\(lpos\)，使得\(max(a_l,a_{l+1},...,a_{lpos-1})<min(a_{lpos},a_{lpos+1},...,a_i)\)。那么区间\([l,i]\)的贡献就是\(dp[l][lpos-1]+i-lpos\)，容易证明，如果分界点在\([lpos, k]\)之间，就会有区间相交的情况出现
时间复杂度\(O(n^2)\)
void work() {
int n;
cin >> n;
vector<int> a(n + 1);
vector<vector<int>> dp(n + 1, vector<int>(n + 1));
rep (i, 1, n) cin >> a[i];
rep (i, 1, n) dp[i][i] = 0;
LL res = 0;
rep (i, 1, n) {
int nxtmn = 1e9 + 7, lpos = i, mn = a[i];
rrep (j, i - 1, 1) {
if (a[j] > mn) {
lpos = j;
mn = min(nxtmn, mn);
nxtmn = 1e9 + 7;
}
else nxtmn = min(nxtmn, a[j]);
dp[j][i] = dp[j][lpos - 1] + i - lpos;
res += dp[j][i];
}
}
cout << res << "\n";
}
D2. Range Sorting (Hard Version)
对于每个连续子序列最终的形态，一定是若干个两两不相交的区间。设连续子序列\([l,r]\)，按照\(max(a[l...k])<min(a[k+1...r])\)可以划分为\([l,k_1],[k_1+1,k_2],...,[k_m+1,r]\)，设最终满足最小代价的区间划分为\([l,p_1],[p_1+1,p_2]...[p_t+1,r]\)。
可以证明\(m=t\)。因为有一个满足条件的\(k\)就意味着代价减一，也就对应着一个不同的\(p\)，所以\(m<=t\)；而每个\(p\)，都有\(max(a[l,p])<min(a[p+1,r])\)（排序后严格递增），所以\(t<=m\)。综上\(m=t\)。
那么总代价就是\((l,r,k)\)三元组的数量
接下来就是找一种划分方式，使得程序能够在合适的时间复杂度下找出所有这样的三元组，一种方式就是枚举\(a_i\)作为\(min(a[k+1...r])\)，感觉这步是最难想的，能想到就能做了。
设\(x\)是最大的满足\(x<i\)且\(a_x<a_i\)，\(z\)是最大的满足\(z<x\)且\(a_z>a_i\)，\(y\)是最小的满足\(y>i\)且\(a_y<a_i\)，那么这部分减少的代价就是\((x-z)*(y-i)\)
对于每个\(i\)，\(x,y\)可以用单调栈预处理出来，\(z\)可以用二分+st表求出。总的时间复杂度\(O(nlognlogn)\)
int n, a[N];
int st[N][21];
int query(int l, int r) {
if (r - l + 1 <= 0) return -1;
int k = log2(r - l + 1);
return max(st[l][k], st[r - (1 << k) + 1][k]);
}
void init_st() {
for (int i = 1; i <= n; i++) st[i][0] = a[i];
for (int j = 1; j <= 20; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
}
void work() {
cin >> n;
rep (i, 1, n) cin >> a[i];
init_st();
vector<int> kpos(n + 1), ypos(n + 1, n + 1);
stack<int> stk;
rep (i, 1, n) {
while (stk.size() && a[i] < a[stk.top()]) {
ypos[stk.top()] = i;
stk.pop();
}
stk.push(i);
}
while (stk.size()) stk.pop();
rrep (i, n, 1) {
while (stk.size() && a[i] < a[stk.top()]) {
kpos[stk.top()] = i;
stk.pop();
}
stk.push(i);
}
LL res = 0;
rep (i, 1, n) res += 1ll * i * (i - 1) / 2;
rep (i, 1, n) {
int l = 0, r = kpos[i] - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (query(mid, kpos[i] - 1) > a[i]) l = mid;
else r = mid - 1;
}
res -= 1ll * (kpos[i] - l) * (ypos[i] - i);
}
cout << res << "\n";
}