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<cstring> #include<cmath> #include<algorithm> #include<cstdio> #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<r;i++) #define repedge(i,x) for(int i=fi[x];i;i=e[i].next) #define maxn 10001000 #define maxm 400400 #define LL long long using namespace std; int rson[maxn],lson[maxn],total=0,n,m,root[maxm],lst[40][2]; LL sz[maxn],sum[maxn]; int pre[maxm],num[maxm],a[maxm]; int getnew() { ++total; sum[total]=sz[total]=lson[total]=rson[total]=0; return total; } void change(int &x,int old,int l,int r,LL y) { //printf("%d %d %d %lld %lld %lld ",x,l,r,sum[old],sz[old],y); x=getnew(); sum[x]=sum[old]+y; sz[x]=sz[old]+1; lson[x]=lson[old]; rson[x]=rson[old]; if (l==r) return; int mid=(l+r)>>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 ",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 ",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: ",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 ",j,lst[j][0],lst[j][1]); // printf(" "); } // rep(i,1,n) printf("%d %d ",i,num[i]); // printf(" "); root[0]=0; rep(i,1,n) { change(root[i],root[i-1],1,n,(LL)num[i]); //printf("%lld %lld ",sum[root[i]],sz[root[i]]); } // rep(i,1,n) { // printf("%d: ",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 ",l,r); LL ans=-(r+l-2)*(r-l+1)/2; l--; //printf("%lld ",ans); //printf("%lld ",ask1(root[r],1,n,r)); ans+=ask1(root[r],1,n,r); //printf("%lld ",ans); if (r<n) ans+=ask2(root[r],1,n,r+1)*r; //printf(" %lld ",ans); if (l>0) ans-=ask1(root[l],1,n,r); //printf("%lld ",ans); if (r<n && l>0) ans-=ask2(root[l],1,n,r+1)*r; printf("%lld ",last=ans); //printf("/----------------------/ "); } return 0; }