P11278 绝世丑角

因为所有的 Nim 积操作都是跟自己操作，所以简化定义。

定义 f(x)=x\otimes x。

你打出了一点表：0,1,3,2,6,7,5,4,13,12,14,15,11,10,8,9。

然后，使用 oeis.org，查询到了这个东西，叫做 nim-square。

观察描述，发现这个东西由每一个的二进制位构成。

比如说：

那对于 2 的幂次如何处理呢？你点进去，发现有另一个东西。

A006017 - OEIS，描述的就是 f(2^i)，点进去，找到 oeis.org/A006017/b006017.txt，是 i\in[0,255] 的表。

好了，你现在能够 O(\log n) 的时间内求出 f(n)。

定义 f^n(x)=f(f^{n-1}(x))。

将随便一个 x 写出来，发现 f^{32}(x)=x。所以有 32 的循环节。

使用线段树的数据结构！

维护每一个区间的区间和，区间异或和。

一共维护 32 个值，表示这个区间整个被操作 [0,31] 次之后的区间和，区间异或和。

然后就是线段树区间修改，区间查询的板子了。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2.5e5+5;
int p[]={1,3,6,13,24,52,103,222,384,832,1648,3552,6237,13563,26511,56906,98304,212992,421888,909312,1596672,3472128,6786816,14567936,25190110,54589881,108036850,232800673,408783316,888883132,1737454078,3729449897};
int n,q,a[MAXN];
inline int f(int x){
    int res=0;
    for(int i=31;i>=0;i--)if(x>>i&1){
        res^=p[i];
    }
    return res;
}
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
struct Tree{
    int tr[2][32],laz;
    inline void init(int x){
        tr[0][0]=tr[1][0]=x;
        for(int i=1;i<=31;i++){
            tr[0][i]=tr[1][i]=f(tr[0][i-1]);
        }
    }
}tr[MAXN<<2];
inline void push_up(int q){
    for(int i=0;i<=31;i++){
        tr[q].tr[0][i]=tr[ls(q)].tr[0][i]+tr[rs(q)].tr[0][i];
        tr[q].tr[1][i]=tr[ls(q)].tr[1][i]^tr[rs(q)].tr[1][i];
    }
}
int X[33],Y[33];
inline void turn(int q,int Tim){
    for(int i=0;i<=31;i++){
        X[i]=tr[q].tr[0][i];
        Y[i]=tr[q].tr[1][i];
    }
    for(int i=0;i<=31;i++){
        tr[q].tr[0][i]=X[(i+Tim)%32];
        tr[q].tr[1][i]=Y[(i+Tim)%32];
    }
}
inline void push_down(int q){
    if(!tr[q].laz)return ;
    turn(ls(q),tr[q].laz);tr[ls(q)].laz+=tr[q].laz;
    turn(rs(q),tr[q].laz);tr[rs(q)].laz+=tr[q].laz;
    tr[q].laz=0;
}
void build(int l,int r,int q){
    if(l==r){
        tr[q].laz=0;
        tr[q].init(a[l]);
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,ls(q)),build(mid+1,r,rs(q));
    push_up(q);
}
void update(int l,int r,int ql,int qr,int q){
    if(ql<=l&&r<=qr){
        turn(q,1);tr[q].laz++;
        return ;
    }
    int mid=l+r>>1;
    push_down(q);
    if(ql<=mid)update(l,mid,ql,qr,ls(q));
    if(mid<qr)update(mid+1,r,ql,qr,rs(q));
    push_up(q);
}
int query0(int l,int r,int ql,int qr,int q){
    if(ql<=l&&r<=qr)return tr[q].tr[0][0];
    int mid=l+r>>1,res=0;
    push_down(q);
    if(ql<=mid)res+=query0(l,mid,ql,qr,ls(q));
    if(mid<qr)res+=query0(mid+1,r,ql,qr,rs(q));
    return res;
}
int query1(int l,int r,int ql,int qr,int q){
    if(ql<=l&&r<=qr)return tr[q].tr[1][0];
    int mid=l+r>>1,res=0;
    push_down(q);
    if(ql<=mid)res^=query1(l,mid,ql,qr,ls(q));
    if(mid<qr)res^=query1(mid+1,r,ql,qr,rs(q));
    return res;
}
signed main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,n,1);
    while(q--){
        int opt,l,r;cin>>opt>>l>>r;
        if(opt==1){
            update(1,n,l,r,1);
        }
        if(opt==2){
            int res=query1(1,n,l,r,1);
            cout<<res<<"\n";
        }
        if(opt==3){
            int res=query0(1,n,l,r,1);
            cout<<res<<"\n";
        }
    }
}