CF1515H Phoenix and Bits解题报告

解题报告

CF1515H Phoenix and Bits解题报告：

更好的阅读体验

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

跑的还挺快，目前cf rk3。

题意

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

• $1\ x\ y\ z$：将大小在$x$到$y$之间的数按位与$x$
• $2\ x\ y\ z$：将大小在$x$到$y$之间的数按位或$x$
• $3\ x\ y\ z$：将大小在$x$到$y$之间的数按位异或$x$
• $4\ x\ y\ z$：查询在$x$到$y$之间有多少个不同的数

$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记录&代码