题解 CF1515H【Phoenix and Bits】

whiteqwq · 2021-05-04 16:31:03 · 题解

CF1515H Phoenix and Bits解题报告：

更好的阅读体验

CF*3500的ds题的第一篇题解，好诶！

跑的还挺快，目前cf rk3。

题意

维护大小为 n 的集合 a ， q 次操作：

1\ x\ y\ z$：将大小在 $x$ 到 $y$ 之间的数按位与 $z
2\ x\ y\ z$：将大小在 $x$ 到 $y$ 之间的数按位或 $z
3\ x\ y\ z$：将大小在 $x$ 到 $y$ 之间的数按位异或 $z

1\leqslant n\leqslant 2\times 10^5,1\leqslant q\leqslant 10^5

分析

神仙ds，类似平衡树的trie高阶操作。

首先考虑只有 3,4 操作应该怎么维护： 3 操作就直接找到当前结点，交换当前结点的左右儿子然后打上 lazy 标记，4 操作就是像在线段树上一样把询问分配到 \log 个区间查询。

void getxor(int dep,int now,int val){
    if(now==0)
        return ;
    if((val>>(dep-1))&1)
        swp(lc[now],rc[now]);
    lazy[now]^=val;
}
int query(int dep,int now,int l,int r,int L,int R){
    if(now==0||R<l||r<L)
        return 0;
    if(L<=l&&r<=R)
        return res[now];
    int mid=(l+r)>>1;
    pushdown(dep,now);
    return query(dep-1,lc[now],l,mid,L,R)+query(dep-1,rc[now],mid+1,r,L,R);
}

然后考虑 1 与 2 操作。

由于每次递归找结点太慢，因此可以直接用一个 split 操作把这些节点“取下来”，然后修改完后再用一个 merge 操作“并上去”。

因为最高位为 20 ，所以不难发现 [\text{and},x,y,z] 操作等价于全部取反， \text{or} 一下 z\ \text{xor}\ 2^{20} ，然后再次全部取反，由于全部取反等价于异或 2^{20} ，所以 \text{and} 可以直接用 \text{or},\text{xor} 代替。

然后是 \text{or} 操作，发现在某一位 \text{or}\ 1 是等价于对它的左儿子 \text{xor} 当前这位，然后合并其左儿子至右儿子的，因此我们递归处理就好了，注意如果可以直接用 \text{xor} 代替 \text{or} 的地方需要直接修改。（即需要修改的二进制位与当前子树的 \text{or} 没有重复的二进制位）

容易知道每次耗费 \log 时间的操作一定会永久删除一个trie树上一个可能的结点，因此时间复杂度为 O((n+m)\log^2 C)

AC记录&代码