自动搬运

查看原文

来自洛谷，原作者为

	command_block 众水皆昂首，饮月唯我一。

搬运于2025-08-24 22:22:08，当前版本为作者最后更新于2021-07-01 07:11:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意 ： 给出一棵 $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 找到所有需要操作的位置。

下面给出这个数据结构的实现 ：

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 传统，不给出完整代码。