题解 P5670 【秘籍-反复异或】

· · 题解

可能更好的体验

在我通过前，这题的正确代码都非常长而且思路比较复杂（也许）。这里说一种简单且易于理解的方法。

考虑到 m 比较小，询问的时候又只考虑最后 m 个二进制位，所以相当于对 2^m 取模。所以数的种类只有 2^m 种，是一个很小的范围。

异或运算是满足消去律的，所以如果一个数 x 对答案产生了贡献，当且仅当它在区间中出现次数为奇数。

我们考虑用bitset维护一个数在一段区间中的出现次数。那么合并相邻两个区间的信息，只需要将两个bitset异或起来即可。

用线段树维护这些bitset，单次查询的时间复杂度为 O(\frac{2^m}{\omega}\log n)。

考虑对区间整体加上某个数对bitset的影响。那么，原来的第 k 位的信息，现在对应的就是第 (k+x)\bmod2^{m} 位的信息了。相当于整体左移了 x 位，再把前面那些大于等于 2^m 的右移 2^m 位，并合并起来。当 m=10 时，这里就可以写成b=(b<<x)|(b>>(1024-x))。

这里更新一个节点的信息是 O(\frac{2^m}{\omega}) 的，在线段树上区间修改时，单次复杂度还要乘上 \log n。区间修改打标记即可。

最后要得到答案，我们有了一个长度为 2^m 的bitset，可以 O(2^m) 判断并计算每位的贡献。

于是得到了一个时间复杂度 O(\frac{2^m(n+q)\log n}{\omega}+2^mq)，空间复杂度 O(2^mn) 的算法。

其中，后面的 O(2^mq) 的查询，可以通过预处理，然后手写bitset并每 32 位一起求答案，这样可以优化到 O(\frac{2^mq}{\omega})。而 STL 的bitset没法直接提取多位信息（我不太会的说）。不过由于时间复杂度瓶颈不在这里，所以使用 STL 的效率也是可以接受的。

这样做的话，可能会因为常数问题而过不去。注意到当区间比较小的时候，区间里的数很少，此时使用bitset进行运算是非常不划算的，因此在区间比较小的时候，进行暴力修改和查询。

这样就可以通过了，代码长度为 1.7\rm KB 左右。

Code：

#include<iostream>
#include<bitset>
using namespace std;
typedef bitset<1024>BitSet;
const int N=1e5+6;
BitSet d[N];int tg[N],n,m,q,a[N];
void build(int l,int r,int o){
    if(r-l+1<=64){
        for(register int i=l;i<=r;++i)cin>>a[i],d[o].flip(a[i]);
    }else{
        const int mid=l+r>>1;
        build(l,mid,o<<1),build(mid+1,r,o<<1|1);
        d[o]=d[o<<1]^d[o<<1|1];
    }
}
inline void pushdown(int o){
    int&x=tg[o];
    d[o<<1]=(d[o<<1]<<x)|(d[o<<1]>>(1024-x));
    d[o<<1|1]=(d[o<<1|1]<<x)|(d[o<<1|1]>>(1024-x));
    (tg[o<<1]+=x)&=1023,(tg[o<<1|1]+=x)&=1023;
    x=0;
}
void modify(int l,int r,int o,const int&L,const int&R,const int&x){
    if(r-l+1<=64){
        const int lx=max(l,L),rx=min(r,R);
        for(register int i=lx;i<=rx;++i)d[o].flip((a[i]+tg[o])&1023),d[o].flip((tg[o]+((a[i]+=x)&=1023))&1023);
    }else
    if(L<=l&&r<=R){
        d[o]=(d[o]<<x)|(d[o]>>(1024-x));
        (tg[o]+=x)&=1023;
    }else{
        if(tg[o])pushdown(o);
        const int mid=l+r>>1;
        if(L<=mid)modify(l,mid,o<<1,L,R,x);
        if(mid<R)modify(mid+1,r,o<<1|1,L,R,x);
        d[o]=d[o<<1]^d[o<<1|1];
    }
}
void query(int l,int r,int o,const int&L,const int&R,BitSet&b){
    if(r-l+1<=64){
        const int lx=max(l,L),rx=min(r,R);
        for(register int i=lx;i<=rx;++i)b.flip((a[i]+tg[o])&1023);
    }else
    if(L<=l&&r<=R)b^=d[o];else{
        if(tg[o])pushdown(o);
        const int mid=l+r>>1;
        if(L<=mid)query(l,mid,o<<1,L,R,b);
        if(mid<R)query(mid+1,r,o<<1|1,L,R,b);
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>q;
    build(1,n,1);
    while(q--){
        int l,r,op,x;
        cin>>op>>l>>r;
        if(op==1){
            cin>>x;
            modify(1,n,1,l,r,x);
        }else{
            static BitSet b;
            b.reset();
            query(1,n,1,l,r,b);
            int ans=0;
            for(register int i=0;i<1024;++i)
                ans^=b[i]*i;
            ans&=(1<<m)-1;
            cout<<ans<<'\n';
        }
    }
    return 0;
}