[DS记录]P5354 [Ynoi2017] 由乃的 OJ

**题意** : 给出一棵 $n$ 个点的树，每个点的包括一个位运算 $opt$ 和一个权值 $x$，位运算有`&`，`|`，`^` 三种。 每次询问包含三个整数 $x,y,z$ ，初始选定一个数 $v$ 。 然后 $v$ 依次经过从 $x$ 到 $y$ 的所有节点，每经过一个点 $i$，$v$ 就变成 $v\ opt_i\ x_i$，所以他想问你，最后到 $y$ 时，希望得到的值尽可能大，求最大值。 给定的初始值 $v$ 必须是在 $[0,z]$ 之间。 每次修改包含三个整数 $x,y,z$，意思是把 $x$ 点的操作修改为 $y$，数值改为 $z$。 $n,m\leq 10^5,w<2^{64}$ ，时限$\texttt{0.25s}$。 ------------ 位运算的每一位是独立的，只需要得到每一位的真值表，然后按位贪心。 用树剖维护，合并真值表时用位运算优化，复杂度 $O\big((n+m)(\log^2n+w)\big)$。实际常数很小，可以通过。 ```cpp #include<algorithm> #include<cstdio> #include<vector> #define pb push_back #define ull unsigned long long #define MaxN 100500 using namespace std; vector<int> g[MaxN]; struct TNode{int p,f,tf;}b[MaxN]; int siz[MaxN],dep[MaxN]; void pfs1(int u) { siz[u]=1; for (int i=0,v;i<g[u].size();i++) if (!siz[v=g[u][i]]){ dep[v]=dep[b[v].f=u]+1; pfs1(v); siz[u]+=siz[v]; if (siz[v]>siz[b[u].p]) b[u].p=v; } } int dfn[MaxN],tp[MaxN],tim; void pfs2(int u,int tf) { tp[dfn[u]=++tim]=u; b[u].tf=tf; if (b[u].p)pfs2(b[u].p,tf); for (int i=0;i<g[u].size();i++) if (!b[g[u][i]].tf) pfs2(g[u][i],g[u][i]); } const ull Bas=18446744073709551615ull; struct TT{ull s0,s1;}a[MaxN<<2][2],I=(TT){0,Bas}; TT operator + (const TT &A,const TT &B) {return (TT){(A.s0&B.s1)|((Bas^A.s0)&B.s0),(A.s1&B.s1)|((Bas^A.s1)&B.s0)};} inline void up(int u){ a[u][0]=a[u<<1][0]+a[u<<1|1][0]; a[u][1]=a[u<<1|1][1]+a[u<<1][1]; } void Init(int op,ull x,TT *a){ if (op==1)a[0]=a[1]=(TT){0,x}; if (op==2)a[0]=a[1]=(TT){x,Bas}; if (op==3)a[0]=a[1]=(TT){x,Bas^x}; } int n,opt[MaxN];ull sx[MaxN]; void build(int l=1,int r=n,int u=1) { if (l==r){Init(opt[tp[l]],sx[tp[l]],a[u]);return ;} int mid=(l+r)>>1; build(l,mid,u<<1); build(mid+1,r,u<<1|1); up(u); } int to,wfop;ull wfc; void chg(int l=1,int r=n,int u=1) { if (l==r){Init(wfop,wfc,a[u]);return ;} int mid=(l+r)>>1; if (to<=mid)chg(l,mid,u<<1); else chg(mid+1,r,u<<1|1); up(u); } int wfl,wfr;TT _R,R; void qry(int l=1,int r=n,int u=1) { if (wfl<=l&&r<=wfr){ _R=wfop ? a[u][1]+_R : _R+a[u][0]; return ; }int mid=(l+r)>>1; if (wfl<=mid)qry(l,mid,u<<1); if (mid<wfr)qry(mid+1,r,u<<1|1); } int lca(int u,int v) { while(b[u].tf!=b[v].tf){ if (dep[b[u].tf]<dep[b[v].tf])swap(u,v); u=b[b[u].tf].f; }return dep[u]<dep[v] ? u : v; } void pqry(int u,int lim) { if (dep[u]<lim)return ; while(lim<dep[b[u].tf]){ wfl=dfn[b[u].tf];wfr=dfn[u]; _R=I;qry();R=wfop ? R+_R : _R+R; u=b[b[u].tf].f; }wfl=dfn[u]-dep[u]+lim;wfr=dfn[u]; _R=I;qry();R=wfop ? R+_R : _R+R; } int m; int main() { scanf("%d%d%*d",&n,&m); for (int i=1;i<=n;i++) scanf("%d%llu",&opt[i],&sx[i]); for (int i=1,u,v;i<n;i++){ scanf("%d%d",&u,&v); g[u].pb(v);g[v].pb(u); }dep[1]=1;pfs1(1);pfs2(1,1); build(); for (int i=1,op,x,y;i<=m;i++){ ull z; scanf("%d%d%d%llu",&op,&x,&y,&z); if (op==2){to=dfn[x];wfop=y;wfc=z;chg();} else { int t=lca(x,y); R=I; wfop=1;pqry(x,dep[t]+1); TT sav=R;R=I; wfop=0;pqry(y,dep[t]); R=sav+R; ull ans=0,buf=0; for (int i=63;i>=0;i--){ bool f0=R.s0>>i&1,f1=R.s1>>i&1; if (f0)ans|=1ull<<i; else if (f1&&(buf|(1ull<<i))<=z) {ans|=1ull<<i;buf|=1ull<<i;} }printf("%llu\n",ans); } }return 0; } ```