题解：P10856 【MX-X2-T5】「Cfz Round 4」Xor-Forces

· · 题解

考虑暴力做法，对于每种 x 维护一棵线段树，表示 a_{i\oplus x} 这个序列，然后就可以做了。

考虑优化，显然在暴力做法中，有很多节点是相同的，考虑合并这些相同的节点。具体的，比如 x=1 和 x=0 两种，只需要用动态开点线段树，把线段树最底层的左右儿子交换一下即可，除了最底层的，上面的直接新建节点。

实现的时候需要注意，每次选择最高的二进制位改变，这样能保证节点个数不会太多。

#include<bits/stdc++.h>
using namespace std;
#define __MY_TEST__ 0
inline int read()
{
    int re=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
    while( isdigit(ch)) re=(re<<3)+(re<<1)+(ch^48),ch=getchar();
    return re*f;
}
const int N=(1<<18)+5,M=N<<5;
int k,m,a[N],rt[N],sum[M],lc[M],rc[M],ls[M],rs[M],tot;
void push_up(int num)
{
    sum[num]=sum[ls[num]]+sum[rs[num]];
    if(rc[ls[num]]==lc[rs[num]]) sum[num]--;
    lc[num]=lc[ls[num]],rc[num]=rc[rs[num]];
}
void build(int &num,int l,int r)
{
    if(!num) num=++tot;
    if(l==r)
    {
        sum[num]=1;
        lc[num]=rc[num]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(ls[num],l,mid);
    build(rs[num],mid+1,r);
    push_up(num);
}
void rever(int lst,int &num,int l,int r,int x)
{
    if(!num) num=++tot;
    if(r-l+1==x*2) ls[num]=rs[lst],rs[num]=ls[lst];
    else
    {
        int mid=(l+r)>>1;
        rever(ls[lst],ls[num],l,mid,x);
        rever(rs[lst],rs[num],mid+1,r,x);
    }
    push_up(num);
}
array<int,3>query(int num,int l,int r,int pl,int pr)
{
    if(l>=pl&&r<=pr) return {sum[num],lc[num],rc[num]};
    int mid=(l+r)>>1;
    if(pr<=mid) return query(ls[num],l,mid,pl,pr);
    if(pl>mid) return query(rs[num],mid+1,r,pl,pr);
    array<int,3>lv=query(ls[num],l,mid,pl,pr),rv=query(rs[num],mid+1,r,pl,pr);
    int sum=lv[0]+rv[0];
    if(lv[2]==rv[1]) sum--;
    return {sum,lv[1],rv[2]};
}
signed main(){
#if __MY_TEST__
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int tp=read();
    k=read(),m=read();
    for(int i=0;i<(1<<k);i++) a[i]=read();
    build(rt[0],0,(1<<k)-1);
    for(int i=1;i<(1<<k);i++)
    {
        int lowbit=1<<(31-__builtin_clz(i));
        rever(rt[i^lowbit],rt[i],0,(1<<k)-1,lowbit);
    }
    int lans=0,nw=0;
    for(int i=1;i<=m;i++)
    {
        int opt=read();
        if(opt==1)
        {
            nw^=read()^(tp*lans);
        }
        else
        {
            int l=read()^(tp*lans),r=read()^(tp*lans);
            if(l>r) swap(l,r);
            cout<<(lans=query(rt[nw],0,(1<<k)-1,l,r)[0])<<'\n';
        }
    }
}