P5354 [Ynoi2017]由乃的OJ
Preface
自己的由乃题一血，写篇题解纪念一下。
Description
给定一颗 \(n\) 个结点的树，每个结点都有一个权值 \(a_i\) 和一个位运算符 \(\mathrm{op}_i\)。
有 \(m\) 次操作，包含以下两种：
- 给定 \(x\)，修改 \(a_x\) 与 \(\mathrm{op}_x\)；
- 给定 \(x,y,z\)，求 \(v\in [0..z]\) 使得 \(v\) 沿点 \(x\) 到点 \(y\) 的路径移动，移动到点 \(i\) 就会进行操作 \(v \ \mathrm{op}_i \ a_i \to v\)，在完成所有操作之后 \(v\) 最大，求出这个最大值。
\(n,m \le 10^5,\mathrm{op} \in \{\mathrm{and,or,xor}\}\)，任意时刻 \(a_i,z < 2^k\)，\(k \le 64\)。
Sol
思路不是那么好想的树剖+线段树。
直接考虑用树剖转换为区间问题。
由于本题中的运算都是位运算，因此每一位是独立的，这一点就可以考虑使用线段树维护某个区间内每一位在 \(v\) 的对应位取 \(0/1\) 时这一位的最终运算结果。
举个例子：假设区间为 \((1,\mathrm{and}),(3,\mathrm {xor}),(2,\mathrm{or})\)，数值转写为二进制后为 \(01,11,10\)，那么 \(v\) 从左往右低到高第 \(i\) 位的取值为 \(j\) 时的运算结果如下：
| \(j=0\) | \(j=1\) | |
|---|---|---|
| \(i=1\) | \(1\) | \(0\) |
| \(i=2\) | \(1\) | \(1\) |
这个信息是可以 \(O(k)\) 合并的，只要把把左边的值代入到右边进行求值即可。
由于从左往右的答案和从右往左的答案不一定一样，并且树剖中线段树维护的区间是在链上从上到下编号的，故在链合并的时候需要两个方向的信息（\(u\) 到 \(\mathrm{LCA}(u,v)\) 为向上，\(\mathrm{LCA(u,v)}\) 到 \(v\) 为向下），因此两个方向的信息都要维护。
我们回到原问题考虑如何计算答案。
我们采用贪心策略，从 \(z\) 范围内的最高位开始贪。考虑到 \(2^x > \sum_{i=1}^{x-1}2^i\)，因此如果在第 \(x\) 位上存在一种取值使得在进行了操作之后结果的这一位上能取到 \(1\) 并且符合值域要求，那么我们就一定能要这一位贪下来，在答案上加上 \(2^x\)。
到此问题就解决了。时间复杂度 \(O(mk\log^2 n)\)。
然后您看到这道题250ms的时限和 \(k=64\) 陷入了沉思。
这复杂度显然跑不过好吧。想办法优化。
方法也很简单：我们充分利用位运算性质，把上述的信息压进 unsigned long long，就把 \(k\) 成功优化掉了。
最终时间复杂度 \(O(m \log^2 n)\)。
细节详见代码。
Tips
- 链合并的细节非常多，详见代码。
Code
#include<cstdio>
#include<algorithm>
const int M=1e5+5;
typedef unsigned long long ull;
inline int read(){int x(0),op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}
inline int ssread(){int x;scanf("%d",&x);return x;}
inline ull uread(){ull x;scanf("%llu",&x);return x;}
#ifndef ONLINE_JUDGE
#define read ssread
#endif
int n,m,K;
struct edge{
int v,nxt;
}e[M<<1];
int etot,h[M];
int fa[M],dep[M],top[M],dfn[M],siz[M],son[M],rev[M],DFN;
ull a[M];
int OP[M];
void dfs1(int u,int f){//树剖第一次dfs
fa[u]=f;dep[u]=dep[f]+1;siz[u]=1;
for(int i=h[u],v;v=e[i].v,i;i=e[i].nxt)if(v!=f){
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void dfs2(int u,int tp){//树剖第二次dfs
dfn[u]=++DFN;rev[DFN]=u;top[u]=tp;
if(!son[u])return;
dfs2(son[u],tp);
for(int i=h[u],v;v=e[i].v,i;i=e[i].nxt)if(v!=son[u]&&v!=fa[u])dfs2(v,v);
}
struct node{//用于记录区间信息的结构体
ull lef0,lef1,rig0,rig1;
/*
lef0：从左开始走，取0得到的值
lef1：从左开始走，取1得到的值
rig0：从右开始走，取0得到的值
rig1：从右开始走，取1得到的值
*/
node(ull x=0,ull y=-1,ull z=0,ull w=-1){lef0=x,lef1=y,rig0=z,rig1=w;}
};
node merge(node x,node y){
return (node){
//这里的逻辑是：枚举靠前区间的值，以此计算靠后区间的值
(~x.lef0&y.lef0)|(x.lef0&y.lef1),
(x.lef1&y.lef1)|(~x.lef1&y.lef0),
(~y.rig0&x.rig0)|(y.rig0&x.rig1),
(y.rig1&x.rig1)|(~y.rig1&x.rig0)
};
}
namespace segtree{//线段树
#define ls (p<<1)
#define rs ((p<<1)|1)
#define mid ((s+t)>>1)
node T[M<<2];
void pushup(int p){
T[p]=merge(T[ls],T[rs]);
}
void setp(int p,ull x,int op){//设置某个点的状态
if(op==1)T[p].lef0=T[p].rig0=0,T[p].lef1=T[p].rig1=x;
else if(op==2)T[p].lef0=T[p].rig0=x,T[p].lef1=T[p].rig1=-1;
else T[p].lef0=T[p].rig0=x,T[p].lef1=T[p].rig1=~x;
}
void build(int p=1,int s=1,int t=n){
if(s==t){
setp(p,a[rev[s]],OP[rev[s]]);
return;
}
build(ls,s,mid);build(rs,mid+1,t);
pushup(p);
}
void modify(int pos,ull x,int op,int p=1,int s=1,int t=n){
if(s==t){
setp(p,x,op);
return;
}
if(pos<=mid)modify(pos,x,op,ls,s,mid);
else modify(pos,x,op,rs,mid+1,t);
pushup(p);
}
node query(int l,int r,int p=1,int s=1,int t=n){
if(l<=s&&t<=r)return T[p];
if(l<=mid){
if(r>mid)return merge(query(l,r,ls,s,mid),query(l,r,rs,mid+1,t));
else return query(l,r,ls,s,mid);
}
else return query(l,r,rs,mid+1,t);
//一定要注意区间的合并问题！
}
}
void mdf(int pos,ull x,int op){
segtree::modify(dfn[pos],x,op);
}
ull qry(int u,int v,ull w){//核心部分：链的合并
node lc,rc;
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]){
lc=merge(segtree::query(dfn[top[u]],dfn[u]),lc);
//细节1：树剖是从下到上跳的，故新的链是不断地并在前面得到的链的前端
u=fa[top[u]];
}
else{
rc=merge(segtree::query(dfn[top[v]],dfn[v]),rc);
v=fa[top[v]];
}
}
bool flg=1;
if(dep[u]<dep[v])std::swap(u,v),std::swap(lc,rc),flg=0;
std::swap(rc.lef0,rc.rig0),std::swap(rc.lef1,rc.rig1);
//细节2：为了链的方向的统一方便合成最终链，需要把靠上（默认为v）的链左右颠倒
node ans=merge(rc,merge(segtree::query(dfn[v],dfn[u]),lc));
if(flg)std::swap(ans.lef0,ans.rig0),std::swap(ans.lef1,ans.rig1);
//细节3：此时的链左端是v右端是u，故需要将答案链左右颠倒；但是如果u,v已经交换了就不用颠倒
ull res=0;
for(int i=K-1;~i;--i){
ull l0=ans.lef0>>i&1,l1=ans.lef1>>i&1;
if(l0)res|=1ull<<i;//可以那就尽量白嫖
else if(l1&&(1ull<<i)<=w)res|=1ull<<i,w-=1ull<<i;//前文提到的贪心结论：能拿高位一定要拿
}
return res;
}
void adde(int u,int v){
e[++etot]=(edge){v,h[u]};
h[u]=etot;
}
signed main(){
n=read();m=read();K=read();
for(int i=1;i<=n;++i)OP[i]=read(),a[i]=uread();
for(int i=1;i<n;++i){
int u=read(),v=read();
adde(u,v);adde(v,u);
}
dfs1(1,1);
dfs2(1,1);
segtree::build();
while(m--){
int op=read(),u=read(),v=read();
ull w=uread();
if(op==1)printf("%llu\n",qry(u,v,w));
else mdf(u,w,v);
}
return 0;
}