怎么这么眼熟 BZOJ 2908 又是nand？ 复杂度？ O(64∗nlog2n) 吃不消吧 然后发现我写的是假题解 什么三十二颗线段树 明明可以压位在一起
orz
维护上面说的这个东西并不需要64*2个bool变量，而是可以压到两个unsigned long long里，分别代表每一位输入为0和每一位输入为1。 将两个合并：若输入为0，经过左变量后某些bit会变成1，这些bit在输出中与”若输入为1”的右变量那些bit保持一致，其余bit与”若输入为0”的右变量那些bit保持一致，可得: c.x0=(a.x0&b.x1)|(~a.x0&b.x0) 另一个同理。c.x1=(a.x1&b.x1)|(~a.x1&b.x0)
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; typedef unsigned long long ull; 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; } inline void read(ull &x){ char c=nc(); for (;!(c>='0' && c<='9');c=nc()); for (x=0;c>='0' && c<='9';x=x*10+(c-'0'),c=nc()); } const int N=100005; struct edge{ int u,v,next; }G[N<<1]; int head[N],inum; inline void add(int u,int v,int p){ G[p].u=u; G[p].v=v; G[p].next=head[u]; head[u]=p; } #define V G[p].v int depth[N],fat[N],size[N]; inline void dfs(int u,int fa){ depth[u]=depth[fa]+1; fat[u]=fa; size[u]=1; for (int p=head[u];p;p=G[p].next) if (V!=fa) dfs(V,u),size[u]+=size[V]; } int pre[N],clk,top[N],back[N]; inline void find(int u,int fa,int z){ pre[u]=++clk; top[u]=z; back[clk]=u; int son=0,maxv=0; for (int p=head[u];p;p=G[p].next) if (V!=fa && size[V]>maxv) maxv=size[son=V]; if (son) find(son,u,z); for (int p=head[u];p;p=G[p].next) if (V!=fa && V!=son) find(V,u,V); } int n,K; ull val[N]; int opt[N]; struct info{ ull x0,x1; info(ull x0=0,ull x1=0):x0(x0),x1(x1) { } info(ull x,int op){ if (op==1) x0=0,x1=x; if (op==2) x0=x,x1=~0ull; if (op==3) x0=x,x1=~x; } friend info operator + (const info& A,const info& B){ return info((A.x0&B.x1)|(~A.x0&B.x0),(A.x1&B.x1)|(~A.x1&B.x0)); } }L[N<<2],R[N<<2]; inline void Build(int x,int l,int r){ if (l==r){ L[x]=R[x]=info(val[back[l]],opt[back[l]]); return; } int mid=(l+r)>>1; Build(x<<1,l,mid); Build(x<<1|1,mid+1,r); L[x]=L[x<<1]+L[x<<1|1],R[x]=R[x<<1|1]+R[x<<1]; } inline void Modify(int x,int l,int r,int t,info a){ if (l==r){ L[x]=R[x]=a; return; } int mid=(l+r)>>1; if (t<=mid) Modify(x<<1,l,mid,t,a); else Modify(x<<1|1,mid+1,r,t,a); L[x]=L[x<<1]+L[x<<1|1],R[x]=R[x<<1|1]+R[x<<1]; } bool tag; info ret; inline void QueryL(int x,int l,int r,int ql,int qr){ if (ql<=l && r<=qr){ if (!tag) ret=L[x]; else ret=ret+L[x]; tag=1; return; } int mid=(l+r)>>1; if (ql<=mid) QueryL(x<<1,l,mid,ql,qr); if (qr>mid) QueryL(x<<1|1,mid+1,r,ql,qr); } inline info QL(int l,int r){ tag=0; QueryL(1,1,n,l,r); return ret; } inline void QueryR(int x,int l,int r,int ql,int qr){ if (ql<=l && r<=qr){ if (!tag) ret=R[x]; else ret=ret+R[x]; tag=1; return; } int mid=(l+r)>>1; if (qr>mid) QueryR(x<<1|1,mid+1,r,ql,qr); if (ql<=mid) QueryR(x<<1,l,mid,ql,qr); } inline info QR(int l,int r){ tag=0; QueryR(1,1,n,l,r); return ret; } inline info Query(int u,int v){ info lret,rret,mret; bool ltag=0,rtag=0; while (top[u]!=top[v]){ if (depth[top[u]]>depth[top[v]]){ info t=QR(pre[top[u]],pre[u]); lret=!ltag?t:lret+t; ltag=1; u=fat[top[u]]; }else{ info t=QL(pre[top[v]],pre[v]); rret=!rtag?t:t+rret; rtag=1; v=fat[top[v]]; } } if (depth[u]<depth[v]) mret=QL(pre[u],pre[v]); else mret=QR(pre[v],pre[u]); info ret; int tag=0; if (ltag) ret=!tag?lret:ret+lret,tag=1; ret=!tag?mret:ret+mret,tag=1; if (rtag) ret=!tag?rret:ret+rret,tag=1; return ret; } int main(){ int Q,order; int x,y; ull z; freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(n); read(Q); read(K); for (int i=1;i<=n;i++) read(opt[i]),read(val[i]); for (int i=1;i<n;i++) read(x),read(y),add(x,y,++inum),add(y,x,++inum); dfs(1,0); find(1,0,1); Build(1,1,n); while (Q--){ read(order); read(x); read(y); read(z); if (order==1){ info t=Query(x,y); int tag=0; ull ans=0; for (int k=K-1;~k;k--){ int maxv=!tag?(z>>k&1):1; if (t.x0>>k&1){ ans+=1ULL<<k; if (maxv==1 && !tag) tag=1; }else{ if (maxv==1 && (t.x1>>k&1)) ans+=1ULL<<k; else if (maxv==1 && !tag) tag=1; } } printf("%llu\n",ans); }else if (order==2){ Modify(1,1,n,pre[x],info(z,y)); } } return 0; }