晚上写了一发主席树回忆了一下。
wa点在线段树求和的l1和l与r1和r看错地方了，直到看得眼睛痛了才发现。
#include <iostream> #include <stdio.h> #include <vector> #include <string.h> #include <algorithm> using namespace std; const int maxn=1e6+7; int cnt; struct ttt{ int l,r,sum; }; int root[maxn]; ttt T[maxn*5]; int X; int C; int update(int l,int r,int &x,int y,int pos){ T[++cnt]=T[y]; x=cnt; int x1=cnt; if(l==r){ T[x1].sum+=X; C=T[x1].sum; return 0; } int mid=(l+r)/2; if(pos<=mid) { update(l,mid,T[x].l,T[y].l,pos); }else{ update(mid+1,r,T[x].r,T[y].r,pos);} T[x1].sum=0; if(T[x1].l) T[x1].sum=T[T[x1].l].sum; if(T[x1].r) T[x1].sum+=T[T[x1].r].sum; } int Sum; int query(int l,int r,int l1,int r1,int t,int num){ if(l1<=l&&r1>=r){ Sum+=T[num].sum;return 0; }else{ int mid=(l+r)/2; if(l1>mid){ if(T[num].r!=0)query(mid+1,r,l1,r1,t,T[num].r); }else if(r1<=mid){ if(T[num].l!=0)query(l,mid,l1,r1,t,T[num].l); }else{ if(T[num].r!=0)query(mid+1,r,l1,r1,t,T[num].r); if(T[num].l!=0)query(l,mid,l1,r1,t,T[num].l); } } } int main(){ int i,j,k,f1,f2,f3,f4,t1,t2,t3,t4,n,m; //freopen("in.txt","r",stdin); cin >> n>> m; C=0; int l1,r1; int ro1=1; for(i=1;i<=m;i++){ scanf("%d",&t1); if(t1==1){ scanf("%d %d",&t2,&X); C=t2^C; update(1,n,root[ro1],root[ro1-1],C); ro1++; }else{ scanf("%d %d %d",&t2,&t3,&t4); l1=t2^C;r1=t3^C; Sum=0; query(1,n,l1,r1,t4,root[t4]); C=Sum; printf("%d\n",Sum); } } return 0; }
