ARC064 C,E 都是简单题，D 猜结论也没啥意思，就不写了。
ARC065 还是比较好的。
D - Connectivity
给定 \(n\) 个点的无向图，有两组连边，互相独立。
询问每个点通过两组连边都能到达的点的数量。
\(1\le n\le 2\times 10^5\)
先给出一种大炮轰蚊子的解法：
用并查集把两组连边的连通块搞出来，写成两个序列，一个连通块对应一个区间。
那么直接上 [CF1093E]Intersection of Permutations，主席树维护一手即可。
然后我就发现我 zz 了，每个点只会在两组连通块里分别出现一次，所以直接 std::map 存一下贡献即可。
时间复杂度 \(\mathcal O(n\log n)\)
Code
// Problem: D - Connectivity
// Contest: AtCoder - AtCoder Regular Contest 065
// URL: https://atcoder.jp/contests/arc065/tasks/arc065_b
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
const int maxn = 2e5 + 5;
int n,m,k;
struct DSU {
int pre[maxn];
DSU() {
memset(pre , 0 , sizeof(pre));
}
void init() {
for(int i = 1;i <= n;++ i)
pre[i] = i;
return ;
}
int find(int x) {
return x == pre[x] ? x : pre[x] = find(pre[x]);
}
}tr[2];
std::map<std::pair<int,int> , int> s;
int main() {
scanf("%d %d %d",&n,&m,&k);
tr[0].init();
tr[1].init();
for(int i = 1;i <= m;++ i) {
int u,v;
scanf("%d %d",&u,&v);
if(tr[0].find(u) == tr[0].find(v))continue ;
tr[0].pre[tr[0].find(v)] = tr[0].find(u);
}
for(int i = 1;i <= k;++ i) {
int u,v;
scanf("%d %d",&u,&v);
if(tr[1].find(u) == tr[1].find(v))continue ;
tr[1].pre[tr[1].find(v)] = tr[1].find(u);
}
for(int i = 1;i <= n;++ i)
++ s[{tr[0].find(i) , tr[1].find(i)}];
for(int i = 1;i <= n;++ i)
printf("%d ",s[{tr[0].find(i) , tr[1].find(i)}]);
return 0;
}
E - Manhattan Compass
题面有丶小长，看洛谷翻译叭qwq
首先，曼哈顿距离很难处理，先转成切比雪夫距离。
发现题目中的状态可以表示成树形结构，答案就是所有节点子树大小之和。
令 \(dis = dist(a,b)\)，对于两点 \((x_i,y_i),(x_j,b_j)\)，它们有连边，当且仅当：
\[|x_i-x_j|\le dis\land |y_i-y_j|=dis \texttt{或} |x_i-x_j|=dis\land |y_i-yj|\lt dis \]二分求出范围，并查集合并节点即可。
代码写挂了，就不放了 qwq。
F - Shuffling
给定一个长为 \(n\) 的 0/1 序列 \(s\)，\(m\) 次操作，第 \(i\) 次操作的区间为 \([l_i,r_i]\)，表示你可以任意重排 \(s_{l_i}\sim s_{r_i}\) 间的字符。保证 \(l_i\) 单调不降。
求最终可能得到的 0/1 序列数量。
\(1\le n,m\le 3\times 10^3,l_i\le l_{i+1}\)
明显是道 DP，支持 \(\mathcal O(nm)\) 级别的时间复杂度。
令 \(c_i\) 表示 \(s_1\sim s_i\) 中 1 的数量。
先考虑 \(m=1,l_1=1,r_1=n\) 的情况：此时答案即为 \(\binom{n}{c_n}\)。
写成 DP（或者说是组合数的递推式），就是 \(f(i,j)=f(i-1,j-1)+f(i-1,j)\)
其中 \(f(i,j)\) 表示前 \(i\) 个位置放 \(j\) 个 1 的方案数，答案为 \(f(n,c_n)\)
考虑当前位是否能放 1，显然它是有边界的。
具体来说，先离线处理出覆盖 \(i\) 的最大右边界，记为 \(R_i\)
考虑上界，最大的情况肯定是前 \(i\) 位放满，但有可能 \(c_{R_i}\lt i\) 放不满，所以应为 \(\min(i,c_{R_i})\)
考虑下界，最小肯定是一个都不放，但有可能 \(R_i-c_{R_i}\lt i\) 放不满 0，所以应为 \(\max(0,i-(R_i-c_{R_i}))\)
然后直接转移即可。时间复杂度 \(\mathcal O(n^2)\)
Code
// Problem: F - Shuffling
// Contest: AtCoder - AtCoder Regular Contest 065
// URL: https://atcoder.jp/contests/arc065/tasks/arc065_d
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
const int maxn = 3e3 + 5;
int n,m,dp[maxn][maxn],maxr[maxn],c[maxn];
char s[maxn];
int main() {
scanf("%d %d %s",&n,&m,s + 1);
for(int i = 1;i <= n;++ i)
c[i] = c[i - 1] + (s[i] ^ '0'),maxr[i] = i;
for(int i = 1;i <= m;++ i) {
int l,r;
scanf("%d %d",&l,&r);
maxr[l] = std::max(maxr[l] , r);
}
for(int i = 1;i <= n;++ i)
maxr[i] = std::max(maxr[i] , maxr[i - 1]);
dp[0][0] = 1;
for(int i = 1;i <= n;++ i) {
int L = std::max(0 , i - (maxr[i] - c[maxr[i]]));
int R = std::min(i , c[maxr[i]]);
for(int j = L;j <= R;++ j) {
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod;
}
}
printf("%d\n",dp[n][c[n]]);
return 0;
}