题目

 

 

分析

 先敲了个树链剖分，发现无法AC（其实是自己弱，懒得debug、手写栈）

然后去学了学正解

核心挺好理解的，$ query(a) $是$ a $到根的异或和。

答案就是$ lca(x,y) \hat{}  query(x)  \hat{}  query(b) $

接着维护异或和，很显然线段树挺容易搞的。

但我们今天学学树状数组来维护异或和

若将区间$ [l,r] $内的元素全部异或x，相当于在第l位标记x，再在第r+1位标记x，

这样，对于第r位以后的元素，这两个命令互相抵消，查询某个元素的值，只需用树状数组把它之前的命令全部累加起来即可。

强无敌了~~~ 

 

 

代码

lca+dfs序+树状数组：

#include 
      
       using namespace std;const int maxn=500005;int fa[maxn][20],depth[maxn],w[maxn];int in[maxn],out[maxn],cnt,vis[maxn],n,bit[maxn];vector
       
         G[maxn];int dfs(int u){    for(int i=1;i<19;i++){        if(depth[u] < (1 << i)) break;        fa[u][i]=fa[fa[u][i-1]][i-1];    }    in[u]=++cnt;    for(int i=0;i
        
         =0;i--){        if(fa[x][i]!=fa[y][i]){            x=fa[x][i]; y=fa[y][i];        }    }    if(x==y) return x;    else return fa[x][0];}void add(int x,int v){
    for(;x<=n;x+=x&-x) bit[x]^=v;}int query(int x){
    int ans=0;for(;x>0;x-=x&-x) ans^=bit[x];return ans;} int main(){    int u,v,q;    scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%d",&w[i]);    for(int i=1;i
        
       
      

 

树链剖分（无法AC）：

#include 
      
       using namespace std;const int maxn=500005;int top[maxn],fa[maxn],son[maxn],dep[maxn],siz[maxn];int wt[2*maxn],w[2*maxn],id[2*maxn],v[2*maxn],cnt,n;vector
       
         G[maxn];void build(int o,int l,int r){    if(l==r){ v[o]=wt[l]; return; }    int mid=l+r>>1;    build(o<<1,l,mid); build(o<<1|1,mid+1,r);    v[o]=v[o<<1]^v[o<<1|1];} void update(int o,int l,int r,int val,int L){    //    printf("--->>>  %d %d %d %d %d\n",o,l,r,val,L);    if(l==r){        v[o]=val; return;    }    int mid=l+r>>1;     if(L<=mid) update(o<<1,l,mid,val,L);     else update(o<<1|1,mid+1,r,val,L);    v[o]=v[o<<1]^v[o<<1|1];}int query(int o,int l,int r,int L,int R){    if(l>R||r
        
         =L&&r<=R){
    return v[o];}    int mid=l+r>>1;    int ans=query(o<<1,l,mid,L,R)^query(o<<1|1,mid+1,r,L,R);    return ans;} ///int dfs1(int x,int f,int depth){    dep[x]=depth; fa[x]=f; siz[x]=1;    int maxnum=0;    for(int i=0;i
         
          dep[y]) swap(x,y);    ans^=query(1,1,n,id[x],id[y]);    return ans;} int main(){//    freopen("1.txt","r",stdin);    //    int __size__=30<<20;  //    char *__p__=(char*)malloc(__size__)+__size__;  //    __asm__("movl %0, %%esp\n"::"r"(__p__));    int u,v,q;    scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%d",&w[i]);    for(int i=1;i