题解：CF1515H Phoenix and Bits

· · 题解

考虑使用 0-1trie 解决，可以将其视作一棵动态开点权值线段树，每个线段树结点向左子树连权值为 0 的边，向右子树连权值为 1 的边。

对 and，or，xor 操作进行分析，单独考虑一个叶子节点在操作后会放在什么位置，发现其相当于将一些父亲的左儿子改为右儿子，右儿子改为左儿子。这会改变树的形态，难以在区间上维护。

为了方便操作，我们把需要操作的区间使用线段树分裂分裂出来，操作完再线段树合并回去，这样可以将区间操作转化为全局操作。

由于每次线段树分裂至多新增 O(\log V) 个节点，每次线段树合并递归都将减少 1 个节点，所以这部分的时间复杂度为 O(n \log V)。

xor 操作相当于将线段树对应的层交换左右儿子，可以打全局 tag。

and 操作可以 or 和 xor 操作替代，定义 U = 2^{20}-1，则 x \& y = ((x \oplus U)|(y \oplus U)) \oplus U。

思考 or 操作后会带来什么变化。

  1. 只有左子树，左子树会放在右子树的位置上。

  2. 只有右子树，没有变化。

  3. 同时具有左子树和右子树，左子树会合并到右子树上。

情况 1，2 可以打 tag 维护。情况 3 需要进行线段树合并，这会使节点数至少减小 1，所以如果能定位到所有情况 3 的节点，均摊复杂度就是正确的。

如果子树内有情况 3 的节点，就暴力递归，否则打 tag 返回。

这需要判断子树内对应深度是否存在节点同时具有左右子树，容易状压维护的。

实现细节上需要注意 or 标记与 xor 标记的下传顺序。

线段树初始有 O(n \log V) 个节点，定位单个节点的复杂度是 O(\log V)，总时间复杂度 O(n \log^2 V)。

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=(1<<20)+5;
struct node{
    int ls,rs,tag1,tag2,isp,sum;
}tr[N<<6];
int n,q,m,md,rt,nt,idx;
int read(){
    int k=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9')
        k=k*10+ch-'0',ch=getchar();
    return k;
}
int merge(int x,int y,int d);
void pushup(int k,int d){
    tr[k].sum=tr[tr[k].ls].sum+tr[tr[k].rs].sum;
    tr[k].isp=((tr[tr[k].ls].isp|tr[tr[k].rs].isp)|(((tr[k].ls!=0&&tr[k].rs!=0)?(1<<d):0)));
}
void change1(int k,int v,int d){
    if((1<<d)&v)
        swap(tr[k].ls,tr[k].rs);
    tr[k].tag1^=v;
}
void change2(int k,int v,int d){
    if((1<<d)&v){
        if(tr[k].ls!=0&&tr[k].rs!=0){
            tr[k].rs=merge(tr[k].rs,tr[k].ls,d-1),tr[k].ls=0;
            pushup(k,d);
        }
        else if(tr[k].ls!=0)
            tr[k].rs=tr[k].ls,tr[k].ls=0;
    }
    tr[k].tag2|=v,tr[k].tag1=(tr[k].tag1&(v^m));
}
void pushdown(int k,int d){
    if(tr[k].tag2){
        change2(tr[k].ls,tr[k].tag2,d-1),change2(tr[k].rs,tr[k].tag2,d-1);
        tr[k].tag2=0;
    }
    if(tr[k].tag1){
        change1(tr[k].ls,tr[k].tag1,d-1),change1(tr[k].rs,tr[k].tag1,d-1);
        tr[k].tag1=0;
    }
}
int merge(int x,int y,int d){
    if((!x)||(!y))
        return x+y;
    if(d<0) return x;
    pushdown(x,d),pushdown(y,d);
    tr[x].ls=merge(tr[x].ls,tr[y].ls,d-1);
    tr[x].rs=merge(tr[x].rs,tr[y].rs,d-1);
    pushup(x,d);
    return x;
}
void build(int &k,int l,int r,int x,int d){
    if(!k) k=++idx;
    if(l==r){
        tr[k].sum=1;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) build(tr[k].ls,l,mid,x,d-1);
    if(mid+1<=x) build(tr[k].rs,mid+1,r,x,d-1);
    pushup(k,d);
}
void split(int &k,int &p,int l,int r,int x,int y,int d){
    if(!k) return;
    if(x<=l&&r<=y){
        p=k,k=0;
        return;
    }
    p=++idx;
    pushdown(k,d);
    int mid=(l+r)>>1;
    if(x<=mid) split(tr[k].ls,tr[p].ls,l,mid,x,y,d-1);
    if(mid+1<=y) split(tr[k].rs,tr[p].rs,mid+1,r,x,y,d-1);
    pushup(k,d),pushup(p,d);
}
int query(int k,int l,int r,int x,int y,int d){
    if(!k) return 0;
    if(x<=l&&r<=y)
        return tr[k].sum;
    pushdown(k,d);
    int mid=(l+r)>>1,res=0;
    if(x<=mid) res+=query(tr[k].ls,l,mid,x,y,d-1);
    if(mid+1<=y) res+=query(tr[k].rs,mid+1,r,x,y,d-1);
    return res;
}
void modify(int k,int d){
    if(!k) return;
    if(d<0) return;
    if(!(tr[k].isp&tr[k].tag2)) return;
    pushdown(k,d);
    modify(tr[k].ls,d-1);
    modify(tr[k].rs,d-1);
    pushup(k,d);
}
int main(){
    int opt,l,r,x;
    n=read(),q=read();
    m=(1<<20)-1,md=19;
    for(int i=1;i<=n;i++)
        x=read(),build(rt,0,m,x,md);
    for(int i=1;i<=q;i++){
        opt=read(),l=read(),r=read();
        if(opt==4)
            printf("%d\n",query(rt,0,m,l,r,md));
        else{
            x=read();
            split(rt,nt,0,m,l,r,md);
            if(opt==1){
                change1(nt,m,md);
                change2(nt,x^m,md);
                modify(nt,md);
                change1(nt,m,md);
            }
            else if(opt==2){
                change2(nt,x,md);
                modify(nt,md);
            }
            else if(opt==3)
                change1(nt,x,md);
            rt=merge(rt,nt,md);
        }
    }
    return 0;
}