2019杭电多校第三场 HDU 6610

题意

给出 $n$n个数，询问一个区间 $[L,R]$[L,R]，在这个区间内找 $[l,r]$[l,r] 做 $NIM$NIM游戏，问先手必胜的 $[l,r]$[l,r] 种类数
首先， $NIM$NIM游戏的判断条件为 ，所有数字的 $xor$xor和大于零就是先手必胜，否则先手必败
根据 $xor$xor的性质，预处理出前缀 $xor$xor和 $C\left[i\right]$C[i]，就可以 $O\left(1\right)$O(1)判断胜负
所以区间 $[l,r]$[l,r]胜负，看 $C[l-1]$C[l−1]和 $C\left[r\right]$C[r]是否相同即可
问题就变为求区间 $[L-1,R]$[L−1,R] 中相同数字的对数
带修改的莫队（三维莫队）上场…
第一次学…
对于每一个区间增加一个版本号，表明是第几次修改之后的
维护时，先将版本号更新到当前询问的，再将左右区间更新到当前序询问的
注意排序的 $cmp$cmp

代码

#include<bits/stdc++.h>
#define N 100010
#define INF 0x3f3f3f3f
#define eps 1e-10
// #define pi 3.141592653589793
#define mod 998244353
#define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;

 
struct query{int l,r,e,id;} q[N];
int n,k,m,tot,blocks,a[N],c[N];LL ans[N];
inline bool cmp(query a,query b)
{
    a.l/=blocks;a.r/=blocks;
    b.l/=blocks;b.r/=blocks;
    if(a.l==b.l)
        return a.r<b.r||(a.r==b.r&&a.e<b.e);
    return a.l<b.l;
}
int e[N];
int num[1<<20];
int main(){
    while(~scc(n,m)){
        blocks=pow(n,2.0/3);
        memset(num,0,sizeof num);
        for(int i=1;i<=n;i++) sc(a[i]),c[i]=c[i-1]^a[i];
        int cnt=0,tot=0;
        for(int i=1,op;i<=m;i++){
            sc(op);
            if (op==1){
                tot++;
                scc(q[tot].l,q[tot].r); q[tot].l--; q[tot].e=cnt; q[tot].id=tot;
            }else
                sc(e[++cnt]);
        }
        sort(q+1,q+tot+1,cmp);
        int l=0,r=0,k=0; LL res=0; num[0]=1;
        for(int i=1;i<=tot;i++)                     
        {
            while(k<q[i].e){
                k++;
                int t=c[e[k]]^a[e[k]]^a[e[k]+1];
                if(l<=e[k] && e[k]<=r){
                    res-=(--num[c[e[k]]]);
                    res+=num[t]++;
                }
                c[e[k]]=t;
                swap(a[e[k]],a[e[k]+1]);
            }
            while(k>q[i].e){
                int t=c[e[k]]^a[e[k]]^a[e[k]+1];
                if(l<=e[k] && e[k]<=r){
                    res-=(--num[c[e[k]]]);
                    res+=num[t]++;
                }
                c[e[k]]=t;
                swap(a[e[k]],a[e[k]+1]);
                k--;
            }
            while(r<q[i].r){
                r++;
                res+=num[c[r]]++;//add
            }
            while(l>q[i].l){
                l--;
                res+=num[c[l]]++;//add
            }
            while(l<q[i].l){
                res-=--num[c[l]];//del
                l++;
            }
            while(r>q[i].r){
                res-=--num[c[r]];//del
                r--;
            }
            LL len=r-l;
            ans[q[i].id]=len*(len+1)/2-res;
        }
        for(int i=1;i<=tot;i++) printf("%lld\n",ans[i]);
    }
}