nand

题目大意

定义A nand B=not(A and B)（运算操作限制了数位位数为K）比如2 nand 3，K=3，则2 nand 3=not (2 and 3)=not 2=5。

给出一棵树，树上每个点都有点权，定义树上从a到b的费用为0与路径上的点的权值顺次nand的结果，例如：从2号点到5号点顺次经过2->3->5，权值分别为5、7、2，K=3，那么最终结果为0 nand 5 nand 7 nand 2=7 nand 7 nand 2=0 nand 2=7。

现在这棵树需要支持以下操作。

① Replace a b:将点a（1≤a≤N）的权值改为b。

② Query a b:输出点a到点b的费用。

请给出一个程序支持这些操作。

Solution

好像是个板子，然后发现nand不满足交换律和结合律

艹！那拿头维护啊！

我们考虑对于二进制位每一位种一棵线段树，然后每个节点\(\{l,r\}\)，维护\(0 nand \{l,r\}\)的值，\(1 nand \{l,r\}\)的值，\(\{l,r\} nand 0\)，\(\{l,r\} nand 1\)的值（都只是这一位上）

然后每次找到a、b的lca，然后对于a到lca上的路径，从右到左查询，然后lca到b，从左到右查询（因为a、b的id均比lca大），记得两边查询不能两边重复查lca，然后两个合并一下就好了

记住query的时候从右到左时要先访问右儿子再访问左儿子。。。我因为这个居然调了1h+。。。

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct qwq{
    int v;
    int nxt;
}edge[200010];
int cnt=-1;
int head[200010];
void add(int u,int v){
    edge[++cnt].nxt=head[u];
    edge[cnt].v=v;
    head[u]=cnt;
}
int fa[200010];
int son[200010];
int top[200010];
int siz[200010];
int tid[200010];
int dep[200010];
int ind;
void dfs1(int u,int ff,int depth){
    fa[u]=ff;
    siz[u]=1;
    dep[u]=depth;
    for(int i=head[u];~i;i=edge[i].nxt){
        int v=edge[i].v;
        if(v==ff)continue;
        dfs1(v,u,depth+1);
        siz[u]+=siz[v];
        if(!son[u]||siz[son[u]]<siz[v])son[u]=v;
    }
} 
void dfs2(int u,int topf){
    tid[u]=++ind;
    top[u]=topf;
    if(son[u]){
        dfs2(son[u],topf);
    } 
    for(int i=head[u];~i;i=edge[i].nxt){
        int v=edge[i].v;
        if(v==fa[u]||v==son[u])continue;
        dfs2(v,v);
    }
}
bool t[800010][33][2][2];//[0][0]:左，0 
int k;
#define ls o<<1
#define rs o<<1|1
void pushup(int o){
    for(int i=0;i<=k;++i){
        t[o][i][0][0]=t[rs][i][0][t[ls][i][0][0]];
        t[o][i][0][1]=t[rs][i][0][t[ls][i][0][1]];
        t[o][i][1][0]=t[ls][i][1][t[rs][i][1][0]];
        t[o][i][1][1]=t[ls][i][1][t[rs][i][1][1]];
    }
}
void update(int o,int l,int r,int x,int val){
    if(l==r){
        int tmp=1;
        for(int i=0;i<=k;++i){
            if((val&tmp)==tmp){
                t[o][i][0][0]=1;
                t[o][i][0][1]=0;
                t[o][i][1][0]=1;
                t[o][i][1][1]=0;
            }
            else {
                t[o][i][0][0]=t[o][i][0][1]=t[o][i][1][0]=t[o][i][1][1]=1;
            }
            tmp<<=1;
        }
        return;
    }
    int mid=(l+r)/2;
    if(x<=mid)update(ls,l,mid,x,val);
    else update(rs,mid+1,r,x,val);
    pushup(o);
}
int ans[33];
void upd(int o,int type){
    for(int i=0;i<=k;++i){
        ans[i]=t[o][i][type][ans[i]];
    }
}
void query(int o,int l,int r,int L,int R,int type){
    if(L>R)return;
    if(L<=l&&r<=R){
        upd(o,type);
        return;
    }
    int mid=(l+r)/2;
    if(type==1){
        if(mid<R)query(rs,mid+1,r,L,R,type);
        if(L<=mid)query(ls,l,mid,L,R,type);
    }
    else {
        if(L<=mid)query(ls,l,mid,L,R,type);
        if(mid<R)query(rs,mid+1,r,L,R,type);
    }
}
int lca(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    return x;
}
int n,m;
void querytree1(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        query(1,1,n,tid[top[x]],tid[x],1);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    query(1,1,n,tid[y],tid[x],1);
}
struct qq{
    int l,r;
}stk[200010];
int tp;
void querytree2(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        stk[++tp].l=tid[top[x]],stk[tp].r=tid[x];
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    stk[++tp].l=tid[y]+1,stk[tp].r=tid[x];
}
int v[200010];
signed main(){
    memset(head,-1,sizeof(head));
    scanf("%lld%lld%lld",&n,&m,&k);
    k--; 
    for(int i=1;i<=n;++i){
        scanf("%lld",&v[i]);
    }
    for(int i=1;i<n;++i){
        int u,v;
        scanf("%lld%lld",&u,&v);
        add(u,v),add(v,u);
    }
    dfs1(1,0,1);
    dfs2(1,1);
    for(int i=1;i<=n;++i){
        update(1,1,n,tid[i],v[i]);
    }
    char que[21];
    for(int i=1;i<=m;++i){
        scanf("%s",que);
        if(que[0]=='Q'){
            int x,y;
            scanf("%lld%lld",&x,&y);
            int LCA=lca(x,y);
            querytree1(x,LCA);
            querytree2(y,LCA);
            for(int j=tp;j>=1;--j)query(1,1,n,stk[j].l,stk[j].r,0);
            tp=0;
            int tmp=0;
            for(int j=0;j<=k;++j){
                tmp+=ans[j]<<j;
            }
            printf("%lld\n",tmp);
            memset(ans,0,sizeof(ans));
        }
        else {
            int u,val;
            scanf("%lld%lld",&u,&val);
            update(1,1,n,tid[u],val);
        }
    }
}