题解 【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 维护颜色出现次数 \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 时，逐层考虑 ：

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

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