省选杂题选做

P5327

容斥这一块奥

显然的一个容斥，选择 \(S\) 集合内部的路径，容斥系数为 \((-1)^{m - |S|}\)，记路径交集的点集为 \(C\)，则提供的贡献为 \((-1)^{m - |S|}\binom{|C|}{2}\)。

性质：\(C\) 必然为联通块，所以考虑点减边容斥。一个比较奇怪的地方在于这里面 \(C\) 作为点集合说明点之间相互影响所以似乎不方便点减边容斥。

所以考虑什么容斥啊歪！

\(\binom{|C|}{2}\) 很难用组合意义做，考虑直接求解：\(x\) 能到的点为包含 \(x\) 的链的并集。

可以使用各种手法如线段树合并维护出来包含 \(x\) 的链编号。已知链的编号，将链的端点取出来按照 \(dfn\) 排序问题就变成了相邻两点距离和。单个点的删改可以做 \(O(\log_2 n)\)，多个点考虑 dsuontree，这题是不是就做完了。

我草时间复杂度好像还是 \(O(n\log^2 n)\) 的有点牛。

这告诉我们不能太魔怔老容斥。

---

P5360

严肃被击杀。

破环为链后问题变成了对于区间 \([l, r]\) 这些列中的点形成网格图求最小生成树。对于这个东西似乎不能线段树分治之类的。考虑直接分治。对于区间分成跨过中间和没有跨过中间的，然后分治，跨国中间的合并。注意到因为所有都跨过第 \(m\) 列，所以只用对它分治一层即可。问题实际上转化成对于 \(m\) 列每个前缀列和后缀列求出 MST，最后合并。

合并 MST 的前提在于：在各自子图中不能成为最小生成树的边一定不会成为全局最小生成树的边。因此合并 MST 相当于加入 \((i, m)-(i, m + 1)\) 这些边，若存在环，那么删除环中最大边权。到这里我就不太会了因为我不知道和之前哪条边形成环，如果要动态维护这件事情必须要 LCT 之类的。看了题解感觉确实很牛哇。

注意到我们并不需要拘泥于维护树的具体形态这件事。同时以后缀的 MST 为例，则一定存在 \((i, m), (j, m)\) 使得被删除的边为 MST 上这两点之间边权最大值。这是因为第一次选中这条最大边后 \((i, m)\) 和 \((j, m)\) 就不可能再次同时出现在一个环中所以一定是最大。建立虚树分析，发现这样的边实际上只有 \(O(n)\) 条（就是以最后一列点建立虚树上的每条边）。也就是说我们可以建立两颗前缀和后缀虚树后，MST 上抛掉虚树边，然后对于这样两颗虚树形成的图和 \(O(n)\) 条边跑 Kurskal。

建立前后缀虚树是 \(O(nm\log n)\) 的，一次询问跑 Kurskal 是 \(O(nq\log n)\) 的。写起来比较需要手法。

总结一下为什么我被击杀了，因为我拘泥于维护树的具体形态，而不是跳开来考虑：真正会删除的边多吗？实际上不多。我们有一些可能不在答案中的边，我们怎么样和已知的部分合并起来？将已知部分看成连通块后 Kruskal。投射到虚树上就是对两颗虚树所有叶子相对连边的图跑 Kruskal。这个虚树和平时建立的还不一样还要把中间点取出来然后重新编号，我觉得这道题的代码实现非常牛，有必要贴出来。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 200, M = 10000;
unsigned int SA, SB, SC;
int lim, n, m;
int getweight() {SA ^= SA << 16;SA ^= SA >> 5;SA ^= SA << 1;unsigned int t = SA;SA = SB;SB = SC;SC ^= t ^ SA;return SC % lim + 1;
}
struct edge {int fr, to, val;bool operator < (const edge &other) const {return val < other.val;}
};
struct mst {int siz;ll sum = 0;vector <edge> vec;mst() {siz = 0, sum = 0;vec.clear();}mst(const int *arr) {siz = n, sum = 0;for(int i = 1; i < n; i++)vec.push_back((edge){i, i + 1, arr[i]});}ll allsum() {ll rest = sum;for(int i = 0; i < vec.size(); i++)rest += vec[i].val;return rest;}
};
mst pre[M + 3], suf[M + 3];int fa[N * 4 + 3];
int Find(int x) {if(x == fa[x]) return x;else return fa[x] = Find(fa[x]);
}int used[N * 4 + 3];
vector <edge> gra[N * 4 + 3];
bool dfs1(int u, int fa) {int sum = 0;for(int i = 0; i < gra[u].size(); i++) {int v = gra[u][i].to;if(v == fa) continue;sum += dfs1(v, u);}if(sum >= 2) used[u] = 1;//若为 LCA，在虚树上，这个猛男写法可以规避掉很多东西，我之前也没有写过，感觉很棒sum += used[u];return sum;
}
vector <edge> vecrest;
ll rsum = 0;
void dfs2(int u, int fa, int last, int val) {if(used[u]) {if(last) vecrest.push_back((edge){used[u], last, val});rsum += val, val = 0, last = used[u];}for(int i = 0; i < gra[u].size(); i++) {int v = gra[u][i].to, w = gra[u][i].val;if(v == fa) continue;dfs2(v, u, last, max(val, w));}
}
mst mergge(const mst &A, const mst &B, int *arr) {//合并 A，B 两个 mstint nn = A.siz + B.siz;for(int i = 1; i <= nn; i++)gra[i].clear(), used[i] = 0, fa[i] = i;mst ans;ans.sum = A.sum + B.sum;vector <edge> vec; vec = A.vec;for(int i = 0; i < B.vec.size(); i++)//右半部分从的点重边号vec.push_back((edge){B.vec[i].fr + A.siz, B.vec[i].to + A.siz, B.vec[i].val});for(int i = 1; i <= n; i++)//我们保证 mst 中最左边的 n 个点是最左边一列，最右边的 n 个点是最右边一列vec.push_back((edge){A.siz - n + i, A.siz + i, arr[i]});sort(vec.begin(), vec.end());for(int i = 0; i < vec.size(); i++) {int u = vec[i].fr, v = vec[i].to, w = vec[i].val;if(Find(u) == Find(v)) continue;ans.sum += w;fa[Find(u)] = Find(v);gra[u].push_back((edge){u, v, w});gra[v].push_back((edge){v, u, w});}//求解 mstfor(int i = 1; i <= nn; i++)used[i] = ((i <= n) || (i >= nn - n + 1));dfs1(1, 0);int rcnt = 0;for(int i = 1; i <= nn; i++)if(used[i]) used[i] = ++rcnt;//对于虚树上的点重边号dfs2(1, 0, 0, 0);ans.vec = vecrest, ans.sum -= rsum, ans.siz = rcnt;vecrest.clear(), rsum = 0;return ans;
}int h[M + 3][N + 3], s[M + 3][N + 3];
int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> m >> SA >> SB >> SC >> lim;for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)h[j][i] = getweight();for(int i = 1; i < n; i++) for(int j = 1; j <= m; j++)s[j][i] = getweight();pre[1] = mst(s[1]);for(int i = 2; i <= m; i++)pre[i] = mergge(pre[i - 1], mst(s[i]), h[i - 1]);suf[m] = mst(s[m]);for(int i = m - 1; i >= 1; i--)suf[i] = mergge(mst(s[i]), suf[i + 1], h[i]);int q; cin >> q;while(q--) {int l, r; cin >> l >> r;cout << (mergge(suf[r + 1], pre[l - 1], h[m])).allsum() << endl;}
}

总结一下

1. MST 合并可以考虑用类似 LCT 的手法，即形成环，断掉最大边这样求解。这是要时刻记住的。
2. 如果树上有用的点很少可以建立虚树。虚树其实也可以用这种手法 \(O(n)\) 建立而且似乎更好写。