先考虑NOI2014的水题，显然从高位到低位贪心，算一下该位取0和1分别得到什么即可。

　　加强这个水题，变成询问区间。那么线段树维护该位取0和1从左到右和从右到左走完这个节点表示的区间会变成什么即可，也滋磁修改了。

　　然后上树，显然树剖即可。非常惨的变成了O(nklog²n)。压一下位就不惨了，变成O(n(k+log²n))。

　　树剖lca都能写挂调一天，不会熟练剖分，退役了。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll unsigned long long#define N 100010char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}ll read(){ ll x=0;char c=getchar(); while (c<'0'||c>'9') c=getchar(); while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x;}ll b[N],gor[N<<2][2],gol[N<<2][2],inf,I;int n,m,k,a[N],p[N],t,cnt;int id[N],dfn[N],top[N],fa[N],son[N],size[N],deep[N];int L[N<<2],R[N<<2];struct data{ int to,nxt;}edge[N<<1];struct data2{ll x,y;};void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}void dfs(int k){ size[k]=1; for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=fa[k]) { fa[edge[i].to]=k; deep[edge[i].to]=deep[k]+1; dfs(edge[i].to); size[k]+=size[edge[i].to]; if (size[edge[i].to]>size[son[k]]) son[k]=edge[i].to; }}void dfs2(int k,int from){ top[k]=from;dfn[k]=++cnt;id[cnt]=k; if (son[k]) dfs2(son[k],from); for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=fa[k]&&edge[i].to!=son[k]) dfs2(edge[i].to,edge[i].to);}ll trans1(ll x,int op,ll y){ if (op==1) return x&y;if (op==2) return x|y;return x^y;}ll trans(ll x,ll t0,ll t1){ return (x&t1)|((~x)&t0);}void up(int k){ gor[k][0]=trans(gor[k<<1][0],gor[k<<1|1][0],gor[k<<1|1][1]); gor[k][1]=trans(gor[k<<1][1],gor[k<<1|1][0],gor[k<<1|1][1]); gol[k][0]=trans(gol[k<<1|1][0],gol[k<<1][0],gol[k<<1][1]); gol[k][1]=trans(gol[k<<1|1][1],gol[k<<1][0],gol[k<<1][1]);}void build(int k,int l,int r){ L[k]=l,R[k]=r; if (l==r) {gol[k][0]=gor[k][0]=trans1(0,a[id[l]],b[id[l]]);gol[k][1]=gor[k][1]=trans1(inf,a[id[l]],b[id[l]]);return;} int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); up(k);}void modify(int k,int x,int op,ll y){ if (L[k]==R[k]) {gol[k][0]=gor[k][0]=trans1(0,op,y);gol[k][1]=gor[k][1]=trans1(inf,op,y);return;} int mid=L[k]+R[k]>>1; if (x<=mid) modify(k<<1,x,op,y); else modify(k<<1|1,x,op,y); up(k);}data2 queryl(int k,int l,int r){ if (L[k]==l&&R[k]==r) return (data2){gol[k][0],gol[k][1]}; int mid=L[k]+R[k]>>1; if (r<=mid) return queryl(k<<1,l,r); else if (l>mid) return queryl(k<<1|1,l,r); else { data2 x=queryl(k<<1|1,mid+1,r),y=queryl(k<<1,l,mid); return (data2){trans(x.x,y.x,y.y),trans(x.y,y.x,y.y)}; }}data2 queryr(int k,int l,int r){ if (L[k]==l&&R[k]==r) return (data2){gor[k][0],gor[k][1]}; int mid=L[k]+R[k]>>1; if (r<=mid) return queryr(k<<1,l,r); else if (l>mid) return queryr(k<<1|1,l,r); else { data2 x=queryr(k<<1,l,mid),y=queryr(k<<1|1,mid+1,r); return (data2){trans(x.x,y.x,y.y),trans(x.y,y.x,y.y)}; }}void solve(ll &t0,ll &t1,int x,int lca){ if (top[x]==top[lca]) { data2 t=queryr(1,dfn[lca],dfn[x]); t0=trans(t0,t.x,t.y),t1=trans(t1,t.x,t.y); return; } solve(t0,t1,fa[top[x]],lca); data2 t=queryr(1,dfn[top[x]],dfn[x]); t0=trans(t0,t.x,t.y),t1=trans(t1,t.x,t.y);}ll jump_query(int x,int y,ll z){ ll t0=0,t1=inf;data2 t;int lca=0,P=x,Q=y; while (top[P]!=top[Q]) { if (deep[top[P]]
           
            dfn[lca]&&dfn[edge[i].to]<=dfn[x]) {t=queryl(1,dfn[edge[i].to],dfn[x]);break;} t0=trans(t0,t.x,t.y),t1=trans(t1,t.x,t.y); } solve(t0,t1,y,lca); ll s=0,c=0; for (int i=k-1;~i;i--) if (t0&(I<