这个题跟树状数组没有半毛钱关系 首先这是一个最低位翻倍的过程，如果这一位最终会变成 0 ，那么步数是 O(logn)的？ 要是这一位不能变成 0 ，也就是在环上跑了，似乎跑到环上的步数也是 O(logn)的？ 然后就变成了，修改要是跑到 0 就暴力跑，跑到环上，询问照样 设某个修改最早到环上的起点是w z×km，那么会对 w′>w,m′=m 且 z,z′,w,w′ 满足一定条件的跑到环上的询问产生贡献，然后就用数据结构维护下
#include<cstdio> #include<cstdlib> #include<algorithm> #include<map> using namespace std; typedef pair<int,int> abcd; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b; } const int M=5000005; int ncnt; int ls[M],rs[M],T[M]; inline void Add(int &x,int l,int r,int t,int a){ if (!x) x=++ncnt; T[x]^=a; if (l==r) return; int mid=(l+r)>>1; if (t<=mid) Add(ls[x],l,mid,t,a); else Add(rs[x],mid+1,r,t,a); } inline int Query(int x,int l,int r,int ql,int qr){ if (!x) return 0; if (ql<=l && r<=qr) return T[x]; int mid=(l+r)>>1,ret=0; if (ql<=mid) ret^=Query(ls[x],l,mid,ql,qr); if (qr>mid) ret^=Query(rs[x],mid+1,r,ql,qr); return ret; } const int N=200005; int K; int cir[N],head[N]; int vst[N],clk,pre[N]; int cnt; int deg[N]; int pos[N],p[N]; int sum[N]; inline void Pre(){ for (int i=1;i<K;i++){ if (vst[i]) continue; int x=i; while (vst[x]!=2 && !cir[x]) vst[x]=2,x=2*x%K; if (cir[x]){ x=i; while (vst[x]==2) vst[x]=1,x=2*x%K; continue; } x=i; while (vst[x]==2) vst[x]=1,x=2*x%K; if (x==0) continue; ++cnt; head[cnt]=x; cir[x]=cnt; x=2*x%K; while (x!=head[cnt]) cir[x]=cnt,x=2*x%K; } for (int i=1;i<=cnt;i++){ for (int x=head[i];;x=2*x%K){ pre[2*x%K]=x; if (2*x%K==head[i]) { p[i]=pos[x]+(2*x>K); break; } pos[2*x%K]=pos[x]+(2*x>K); } sum[i]=sum[i-1]+p[i]; } } int rt[32][N]; #define P(x,y) (sum[(x)-1]+(y)+1) map<int,int> Map; map<abcd,int> Map2; int m,c; inline int lowbit(int n){ m=1; c=0; while (n%K==0) n/=K,m*=K,c++; return n%K*m; } int n,Q; inline int Query(int x){ int l=lowbit(x),ans=0; if (!cir[l/m]){ if (Map.count(x)) ans=Map[x]; }else{ int z=l/m,w=x/(m*K); int cc=cir[z]; ans^=Query(rt[c][P(cc,(w+p[cc]-pos[z])%p[cc])],0,1<<30,0,w-1); int t=z; while (pos[t]==pos[z]){ ans^=Map2[abcd(w,t*m)]; if (pre[t]*2>K) break; t=pre[t]; } } //printf("%d\n",ans); return ans; } int main(){ int order,x,y; freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(n); read(Q); read(K); Pre(); while (Q--){ read(order); read(x); if (order==1){ read(y); int l=lowbit(x); while (x<=n && !cir[l/m]){ Map[x]^=y; x+=l; l=lowbit(x); } if (x>n) continue; int z=l/m,w=x/(m*K); int cc=cir[z]; Add(rt[c][P(cc,(w+p[cc]-pos[z])%p[cc])],0,1<<30,w,y); Map2[abcd(w,z*m)]^=y; }else{ int ret=0; for (int i=x;i;i-=lowbit(i)) ret^=Query(i); printf("%d\n",ret); } } return 0; }