被数论搞自闭了，于是来搞数据结构……
例题：雨天的尾巴
基础操作是，求出 (x) 到 (y) 的 ( extbf{lca}) ，进行树上差分，最后统计答案。但是怎么存储呢？
首先想，给每一个点开一个桶，在操作时给相应的粮食种类加一。然而这样数组要开10w*10w，炸了。
所以引出正解：给每一个点开一个动态开点线段树，每个点的每个线段树结点维护编号 (l sim r) 的粮食中拥有最多的是哪个，以及这个粮食有多少个。每次修改就和普通线段树一样 ( ext{updat}) 和 ( ext{pushup}) 。
动态开点就是一开始先不建线段树点，等到需要了再建。所以这里的儿子关系不是 (o*2) 和 (o*2+1) 了，要用专门的结构体来存一个节点的儿子们编号分别是什么。
这样虽然每次插入要耗费最多 ( ext{O(log n)}) 的空间，但是因为一开始不用空间，所以总的空间是 ( ext{O(n log n)})，是可以的。
最后把线段树合并起来就行了。
一般有两种合并方式：把儿子点的线段树合并到自己身上；或者新开一个线段树，把信息合并到那里。前者会使得自己原来的信息删除，但是后者会耗费许多空间。
本题因为是树上差分，合并后不用管原来的信息了，所以使用第二种方式。
具体实现：（设把 线段树2 合并到 线段树1 上；节点指线段树上某个 (lsim r) 的节点）
如果某节点 线段树1 和 线段树2 都没有，那么返回 0 。
如果某节点只有 线段树1 有，那么返回 线段树1 的这个节点。线段树2 同理。
如果某节点两个线段树都有，那么递归儿子们，并 ( ext{pushup}) 。
int do_merge(int o1,int o2){
if(!o2)return o1;//YKI
if(!o1)return o2;//YKI
if(tre[o1].l==tre[o1].r){//如果递归到的是最底层线段树节点
tre[o1].maxx+=tre[o2].maxx;
tre[o1].maxn=tre[o1].l;
return o1;
}
tre[o1].lv=do_merge(tre[o1].lv,tre[o2].lv);//递归+更新左儿子编号
tre[o1].rv=do_merge(tre[o1].rv,tre[o2].rv);//递归+更新右儿子编号
puhigh(o1);//push up
return o1;
}
而外边是这样的：（上面是遍历两个线段树，而这个是在原始的树上跑）
void merge(int o,int fa){
mar(o){
if(v==fa)continue;
merge(v,o);
do_merge(o,v);//合并o与儿子，注意o保留
}
if(tre[o].maxx>0)ans[o]=tre[o].maxn;
//一定要至少有一袋粮食才能更新，原因显然。
}
细节
-
我先在每一个点上建出其线段树的根，这样有 (rot_i=i) ，而且在后面也方便许多。
-
pushup的时候，如果线段树左儿子的最大值等于右儿子的最大值，那么左儿子优先，因为左儿子存储的编号 (l sim mid) 肯定比右儿子的 (mid+1 sim r) 更小。 -
if(tre[o].maxx>0)ans[o]=tre[o].maxn;，至少要有粮食才能统计答案。
代码
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define per(i,x,y) for(int i=x;i>=y;i--)
#define mar(o) for(int E=fst[o];E;E=e[E].nxt)
#define v e[E].to
using namespace std;
const int n7=101234,m7=201234,t7=6001234;
struct dino{int to,nxt;}e[m7];
struct elep{int l,r,lv,rv,maxx,maxn;}tre[t7];
int n,T,ecnt,fst[n7],dep[n7],fc[n7][23],cnt,ans[n7];
void edge(int sta,int edn){
ecnt++;
e[ecnt]=(dino){edn,fst[sta]};
fst[sta]=ecnt;
}
void dfs(int o){
rep(i,1,20)fc[o][i]=fc[ fc[o][i-1] ][i-1];
mar(o){
if(dep[v])continue;
dep[v]=dep[o]+1;
fc[v][0]=o;
dfs(v);
}
}
int do_lca(int x,int y){
if(dep[x]<dep[y])x^=y^=x^=y;
per(i,20,0){
if(dep[ fc[x][i] ]>=dep[y])x=fc[x][i];
}
if(x==y)return x;
per(i,20,0){
if(fc[x][i]!=fc[y][i])x=fc[x][i],y=fc[y][i];
}
return fc[x][0];
}
void puhigh(int o){
if(tre[ tre[o].lv ].maxx>=tre[ tre[o].rv ].maxx){
tre[o].maxx=tre[ tre[o].lv ].maxx;
tre[o].maxn=tre[ tre[o].lv ].maxn;
}
else{
tre[o].maxx=tre[ tre[o].rv ].maxx;
tre[o].maxn=tre[ tre[o].rv ].maxn;
}
}
void updat(int o,int bag,int val){
if(tre[o].l==tre[o].r){
tre[o].maxx+=val;
tre[o].maxn=tre[o].l;
return;
}
int mid=(tre[o].l+tre[o].r)>>1;
if(bag<=mid){
if(!tre[o].lv){
cnt++,tre[o].lv=cnt;
tre[cnt]=(elep){tre[o].l,mid};
}
updat(tre[o].lv,bag,val);
}
if(bag>=mid+1){
if(!tre[o].rv){
cnt++,tre[o].rv=cnt;
tre[cnt]=(elep){mid+1,tre[o].r};
}
updat(tre[o].rv,bag,val);
}
puhigh(o);
}
int do_merge(int o1,int o2){
if(!o2)return o1;
if(!o1)return o2;
if(tre[o1].l==tre[o1].r){
tre[o1].maxx+=tre[o2].maxx;
tre[o1].maxn=tre[o1].l;
return o1;
}
tre[o1].lv=do_merge(tre[o1].lv,tre[o2].lv);
tre[o1].rv=do_merge(tre[o1].rv,tre[o2].rv);
puhigh(o1);
return o1;
}
void merge(int o,int fa){
mar(o){
if(v==fa)continue;
merge(v,o);
do_merge(o,v);
}
if(tre[o].maxx>0)ans[o]=tre[o].maxn;
}
int main(){
scanf("%d%d",&n,&T);
rep(i,1,n)tre[i]=(elep){1,100000};
cnt=n;
rep(i,1,n-1){
int sta,edn;
scanf("%d%d",&sta,&edn);
edge(sta,edn);
edge(edn,sta);
}
dep[1]=1,dfs(1);
while(T--){
int x,y,bag,lca;
scanf("%d%d%d",&x,&y,&bag);
lca=do_lca(x,y);
updat(x,bag,1),updat(y,bag,1);
updat(lca,bag,-1),updat(fc[lca][0],bag,-1);
}
merge(1,0);
rep(i,1,n)printf("%d
",ans[i]);
return 0;
}
一些优化
- 可以把 (l,r) 放进递归参数里而非结构体里，可以减少空间（即
struct elep{int lv,rv,maxx,maxn;}tre[t7];,updat(int o,int l,int r,int bag,int val),do_merge(int o1,int o2,int l,int r)），改进后评测记录 例题减少了约 40M 的空间！
其它练手题目
Lom 同理，线段树维护的是颜色个数最大值是多少，以及编号和（不用管到底是哪些颜色）。
Promotion 同理，首先离散化，然后建的是权值线段树。