题解 【P6580 [Ynoi2019] 美好的每一天~ 不连续的存在】

**题意** ： 给出一棵 $n$ 个节点的树，每个点有一个颜色，颜色为 $1$ 到 $c$ 的整数。再给出权值数组 $A_{1\sim c}$。 有 $m$ 次查询，每次查询树上只保留 $[l,r]$ 内的所有节点，设一个极大连通块中出现奇数次数的颜色个数为 $t$，则其对答案的贡献为 $A_t$ ，即答案是所有连通块贡献的和，询问间互相独立。 允许离线，$n,m\leq 10^5,c\leq 10^4$ ，时限 $\texttt{3s}$，空限$\texttt{64M}$。 ------------ 使用回滚莫队。 注意到权值数组是不规则的，只能采取较为暴力的做法。 - ## bitset! 每个点的复杂度权重为其度数，按权重将序列分块。 用 `bitset` 维护颜色出现次数 $\bmod~2$ 的结果。这样支持 $O(c/w)$ 合并两个联通块，并查询出现了奇数次的颜色数。 回滚莫队将问题转化为 $O(n\sqrt{m})$ 次联通块合并。复杂度 $O(n\sqrt{m}c/w)$ ，显然无法通过。 还有个问题， $n$ 个 bitset 的空间高达 $O(nc/w)$ ，也无法承受。 - ## 线段树合并！ 我们发现，回滚莫队的右指针单调向右移动，此处发生的合并可以用线段树合并维护（还有并查集），于是一趟从左到右的合并被优化到了 $O(n\log c)$。 处理左指针时，可以沿用线段树合并，保留副本，$\rm xor$ 两次即可撤销贡献。 左指针的复杂度是暴力吗？ 考虑“向集合 $[l+1,r]$ 中插入点 $l$ ”的复杂度，由于图是一棵树，这肯定小于“向 $[l+1,n]$ 中插入点 $l$ ”的复杂度。 于是，将 $l$ 的复杂度权重加上“向 $[l+1,n]$ 中插入点 $l$ 的复杂度”，不难发现，这个权重的总和等价于从后往前的一次合并，是 $O(n\log c)$ 的。 按照这个权重来分块，即可做到 $O(n\sqrt{m}\log c)$。 这个复杂度看起来很对劲，但由于线段树合并的常数较大，难以通过。 - ## 启发式合并！位运算魔改线段树！ 把线段树合并换成启发式合并，复杂度同样是正确的。注意到按秩合并并查集也是启发式合并，这样实现会很方便。 但我们似乎并没有合适的数据结构。`std::set` 的启发式合并是 $O(\log^2)$ 的， $\text{Hash Table}$ 的理论复杂度正确，但常数实在太大。 注意到 $c$ 较小，可以设计一种特殊的基于位运算的数据结构 ： 这个数据结构有三层，是一个树形结构。 底层是若干 `uint` ，用于保存颜色出现次数的奇偶性。 第二层每个节点分为 $32$ 叉，用一个 `uint` 记录每个分支中是否有值。 将二三层绑定在一起，不动态开点，这样第二层就不需要记录儿子指针，可以直接 $O(1)$ 调用任意一个儿子。 第一层分为 `10` 叉，同样用一个 `uint` 记录每个分支中是否有值。 不同于第二层的是，为了节省空间，此处需要记录儿子指针。 能够发现，单元素集合占用的空间是“一个第二层节点与其子树”，是 $32$ 个 `uint` 。而树根占用的空间是 $10$ 个指针。这样就可以卡进空间限制。 将集合 $S_1$ 合并到 $S_2$ 时，逐层考虑 ： - 对于第一层，若 $S_1$ 有某个分支且 $S_2$ 没有，则拷贝指针。 - 若两个第二层合并，容易用第二层上的 `uint` 找到所有需要操作的位置。 下面给出这个数据结构的实现 ： ```cpp const uint Bas=4294967295u; struct BitBlo{ //第二层和第三层 int cnt;uint rt,buf[32]; void clear(){ while(rt){ int p=__builtin_ctz(rt); rt^=(1u<<p);buf[p]=0; }cnt=0; } void build(int x){ rt=(1u<<(x>>5)); buf[x>>5]=(1u<<(x&31)); cnt=1; } }T[MaxN];int tot; void Sxor(BitBlo &A,const BitBlo &B) { //合并两个第二层节点 uint rt=A.rt&B.rt,rt2=(Bas^A.rt)&B.rt; while(rt){ int p=__builtin_ctz(rt);rt^=(1u<<p); A.cnt-=__builtin_popcount(A.buf[p]); A.cnt+=__builtin_popcount(A.buf[p]^=B.buf[p]); if (!A.buf[p])A.rt^=(1u<<p); //在用 xor 代替撤回时，这个删除判断是必须的 } while(rt2){ int p=__builtin_ctz(rt2);rt2^=(1u<<p); A.cnt+=__builtin_popcount(A.buf[p]=B.buf[p]); A.rt|=(1u<<p); } } struct Bitset{ //第一层 uint rt;int t[10],cnt; void clear(){ while(rt){ int p=__builtin_ctz(rt); rt^=(1u<<p);t[p]=0; }cnt=0; } inline void build(int x){ T[t[x>>10]=++tot].build(x&1023); rt=(1u<<(x>>10));cnt=1; } }S[MaxN]; void Sxor(Bitset &A,const Bitset &B) { //合并两棵树 uint rt=A.rt&B.rt,rt2=(Bas^A.rt)&B.rt; while(rt){ int p=__builtin_ctz(rt);rt^=(1u<<p); if (A.t[p]==B.t[p]){ A.cnt-=T[A.t[p]].cnt; A.t[p]=0;A.rt^=(1u<<p); //这只会在用 xor 代替撤回时触发，将拷贝过去的指针撤回 }else { A.cnt-=T[A.t[p]].cnt; Sxor(T[A.t[p]],T[B.t[p]]); A.cnt+=T[A.t[p]].cnt; } } while(rt2){ int p=__builtin_ctz(rt2);rt2^=(1u<<p); A.cnt+=T[A.t[p]=B.t[p]].cnt; A.rt|=(1u<<p); } } ``` 有点卡常，我卡了一个下午，后来晚高峰搭神机才过…… 又优化了一下写法（去掉了原本的 `ull`），可以做到最大点 `2.35s` 。 根据 Ynoi 传统，不给出完整代码。