P5354 [ynoi2017] yoyo OJ (tree section and bit operation)

Preface

When thinking about violence and solving problems “ violence ” Different time , If you continue to think about optimization, you tend to drift away …
So when there is no clue , Have the courage to jump out of the original transformation ！

This optimization of the bit operation type always seems not to be in my register … Need to strengthen ！

analysis

It's not hard to think of a place - by - place $O(nk{\log }^{2}n)$ Tree section method of （LCT You can just log）.
Consider such an implementation ：$f_{0/1}$ It means that a person turned out to be 0/1 The current value .
Merge ：$f_{op}=f_{r,f_{l,op}}$
We can write it in the following form ：$f_{op}=(f_{l,op}\&f_{r,1})|((f_{l,op}\oplus 1)\&f_{r,0})$.
Then we can put 64 A Boolean is pressed into a unsigned long long, To quickly merge .
In this way, the complexity of k Take it off , Time complexity $O(n{\log }^{2}n)$.

Code

1ull<<i It's written in 1<<i WA For a long time …

#include<bits/stdc++.h>
#include<string>
using namespace std;
#define ll long long
#define ull unsigned ll
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")

inline ll read() {
    
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)) {
    if(c=='-') f=-1;c=getchar();}
  while(isdigit(c)) {
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}
const int N=1e5+100;
const int mod=998244353;

bool mem1;

int n,m,k;

int op[N];
ull w[N],o;
int dep[N],siz[N],hson[N],top[N],fa[N],dfn[N],pos[N],tim;
vector<int>e[N];
void dfs1(int x,int f){
    
  siz[x]=1;
  dep[x]=dep[f]+1;
  fa[x]=f;
  for(int to:e[x]){
    
    if(to==f) continue;
    dfs1(to,x);
    if(siz[to]>siz[hson[x]]) hson[x]=to;
    siz[x]+=siz[to];
  }
  return;
}
void dfs2(int x,int tp){
    
  top[x]=tp;
  dfn[++tim]=x;pos[x]=tim;
  if(hson[x]) dfs2(hson[x],tp);
  for(int to:e[x]){
    
    if(to==fa[x]||to==hson[x]) continue;
    dfs2(to,to);
  }
  return;
}

#define mid ((l+r)>>1)
#define ls (k<<1)
#define rs (k<<1|1)
struct node{
    
  ull w[2];
};
node operator + (const node &x,const node &y){
    
  node o;
  o.w[0]=(x.w[0]&y.w[1])|((~x.w[0])&y.w[0]);
  o.w[1]=(x.w[1]&y.w[1])|((~x.w[1])&y.w[0]);
  return o;
}
node tr1[N<<2],tr2[N<<2];
inline void pushup(int k){
    
  tr1[k]=tr1[ls]+tr1[rs];
  tr2[k]=tr2[rs]+tr2[ls];
}
void build(int k,int l,int r){
    
  if(l==r){
    
    int x=dfn[l];
    if(op[x]==1){
    
      tr1[k]=tr2[k]=(node){
    0,w[x]};
    }
    else if(op[x]==2){
    
      tr1[k]=tr2[k]=(node){
    w[x],o};
    }
    else if(op[x]==3){
    
      tr1[k]=tr2[k]=(node){
    w[x],o^w[x]};
    }
    //printf("k=%d (%d %d) %llu %llu\n",k,l,r,tr1[k].w[0],tr1[k].w[1]);
    return;
  }
  build(ls,l,mid);
  build(rs,mid+1,r);
  pushup(k);
  //printf("k=%d (%d %d) %llu %llu\n",k,l,r,tr1[k].w[0],tr1[k].w[1]);
}
void upd(int k,int l,int r,int p){
    
  if(l==r){
    
    int x=dfn[l];
    if(op[x]==1){
    
      tr1[k]=tr2[k]=(node){
    0,w[x]};
    }
    else if(op[x]==2){
    
      tr1[k]=tr2[k]=(node){
    w[x],o};
    }
    else if(op[x]==3){
    
      tr1[k]=tr2[k]=(node){
    w[x],o^w[x]};
    }
    return;
  }
  if(p<=mid) upd(ls,l,mid,p);
  else upd(rs,mid+1,r,p);
  pushup(k);
}
node ask(int k,int l,int r,int x,int y,int op){
    
  //if(k==1) printf("ask: (%d %d) op=%d\n",x,y,op);
  if(x<=l&&r<=y){
    
    if(op==1) return tr1[k];
    else return tr2[k];
  }
  if(y<=mid) return ask(ls,l,mid,x,y,op);
  else if(x>mid) return ask(rs,mid+1,r,x,y,op);
  else if(op==1) return ask(ls,l,mid,x,y,op)+ask(rs,mid+1,r,x,y,op);
  else return ask(rs,mid+1,r,x,y,op)+ask(ls,l,mid,x,y,op);
}
#undef mid
#undef ls
#undef rs

node query(int x,int y){
    
  node res1=(node){
    0,o},res2=(node){
    0,o};
  while(top[x]!=top[y]){
    
    if(dep[top[x]]>=dep[top[y]]){
    
      res1=res1+ask(1,1,n,pos[top[x]],pos[x],2);
      x=fa[top[x]];
    }
    else{
    
      res2=ask(1,1,n,pos[top[y]],pos[y],1)+res2;
      y=fa[top[y]];
    }
  }
  if(dep[x]>=dep[y]) res1=res1+ask(1,1,n,pos[y],pos[x],2);
  else res2=ask(1,1,n,pos[x],pos[y],1)+res2;
  return res1+res2;
}  

bool mem2;
signed main() {
    
#ifndef ONLINE_JUDGE
  freopen("a.in","r",stdin);
  freopen("a.out","w",stdout);
#endif
  n=read();m=read();k=read();
  if(k==0) o=0;
  else{
    
    o=1;
    for(int i=0;i<k;i++) o=(o<<1)|1;
  }
  for(int i=1;i<=n;i++) scanf("%d%llu",&op[i],&w[i]);
  for(int i=1;i<n;i++){
    
    int x=read(),y=read();
    e[x].push_back(y);
    e[y].push_back(x);
  }
  dfs1(1,0);
  dfs2(1,1);
  build(1,1,n);
  for(int i=1;i<=m;i++){
    
    int oop,x,y;
    ull z;
    scanf("%d%d%d%llu",&oop,&x,&y,&z);
    if(oop==2){
    
      op[x]=y;w[x]=z;
      upd(1,1,n,pos[x]);
    }
    else{
    
      node o=query(x,y);
      //printf("%llu %llu\n",o.w[0],o.w[1]);
      ull res(0);
      for(int i=k-1;i>=0;i--){
    
	if(o.w[0]&(1<<i)) res+=(1<<i);
	else if((o.w[1]&(1<<i))&&z>=(1<<i)){
    
	  z-=(1<<i);
	  res+=(1<<i);
	}
      }
      printf("%llu\n",res);
    }
  }
  return 0;
}
/* 3 1 2 3 3 1 1 1 */