https://odzkskevi.qnssl.com/f0fbdb108ec813b1294f8f714805963b?v=1502083692

 

网上搜到的题解：

http://blog.csdn.net/zzkksunboy/article/details/76563303

xor的题，一般是考虑第一个不一样的位。

这个题当时考虑都是从字典树解决。这题可以对每个左边界找到最远的右边界，记作数组num[i]。

答案算两个部分，一个是num[i](l<=i<=r)小于等于r的，一个是num[i](l<=i<=r)大于r，第二部分答案要变成r。强制在线用主席树。

 

#include
      
       #include
       
        #include
        
         #include
         
          #define rep(i,l,r) for(int i=l;i<=r;i++)#define dow(i,l,r) for(int i=r;i>=l;i--)#define rep0(i,r) for(int i=0;i
          
           >1;    if (y<=mid) change(lson[x],lson[old],l,mid,y);    else change(rson[x],rson[old],mid+1,r,y);}LL ask1(int x,int l,int r,int y){    //printf("%d %d %d %lld %d %lld\n",x,l,r,sum[x],lson[x],sum[lson[x]]);    if (!x) return 0;    if (l==r) return sum[x];    int mid=(l+r)>>1;    if (y<=mid) return ask1(lson[x],l,mid,y);    return sum[lson[x]]+ask1(rson[x],mid+1,r,y);}LL ask2(int x,int l,int r,int y){    if (!x) return 0;    if (l==r) return sz[x];    int mid=(l+r)>>1;    if (y<=mid) return sz[rson[x]]+ask2(lson[x],l,mid,y);    return ask2(rson[x],mid+1,r,y);}void pput(int x,int l,int r){    printf("%d %d %d %lld %lld\n",x,l,r,sum[x],sz[x]);    if (l==r) return;    int mid=(l+r)>>1;    pput(lson[x],l,mid);    pput(rson[x],mid+1,r);}int main(){  //  freopen("1.in","r",stdin);    scanf("%d",&n);    sum[0]=sz[0]=lson[0]=rson[0]=0;    pre[0]=0;    rep(i,1,n) {        scanf("%d",&a[i]);        pre[i]=pre[i-1]^a[i];    }    rep0(i,31) lst[i][0]=lst[i][1]=n;    dow(i,1,n) {      //  printf("%d:\n",i);        int ch1,ch2;        if (a[i+1]) {            dow(j,0,30) {                ch1=(pre[i]>>j)&1;                ch2=(pre[i+1]>>j)&1;                if (ch1!=ch2) {                    lst[j][ch2]=i;                    break;                }            }        }        num[i]=n;        dow(j,0,30) {            ch1=(pre[i-1]>>j)&1;            num[i]=min(num[i],lst[j][ch1]);        }      //  rep(j,0,4) printf("%d %d %d\n",j,lst[j][0],lst[j][1]);      //  printf("\n");    }   // rep(i,1,n) printf("%d %d\n",i,num[i]);   // printf("\n");    root[0]=0;    rep(i,1,n) {        change(root[i],root[i-1],1,n,(LL)num[i]);        //printf("%lld %lld\n",sum[root[i]],sz[root[i]]);    }   // rep(i,1,n) {   //     printf("%d:\n",i);   //     pput(root[i],1,n);   // }    LL last=0,ans=0;    scanf("%d",&m);    while (m--) {        LL l,r;        scanf("%lld %lld",&l,&r);        l=(l+last)%n+1;        r=(r+last)%n+1;        if (l>r) swap(l,r);        //printf("%lld %lld\n",l,r);        LL ans=-(r+l-2)*(r-l+1)/2;        l--;        //printf("%lld\n",ans);        //printf("%lld\n",ask1(root[r],1,n,r));        ans+=ask1(root[r],1,n,r);        //printf("%lld\n",ans);        if (r
           
            0) ans-=ask1(root[l],1,n,r); //printf("%lld\n",ans); if (r
            
             0) ans-=ask2(root[l],1,n,r+1)*r; printf("%lld\n",last=ans); //printf("/----------------------/\n"); } return 0;}