权值线段树
就是把类型存在线段树上，每个下标存的是类型的数量。
可以用来做离线的平衡树，如果值域范围小的话可以在线，只有一只 \(\log\)。
平衡树六种操作：
- 插入 \(x\)
就是把 \(x\) 上的值加 \(1\)。modify(1,1,n,x,1); - 删除一个 \(x\)
就是把 \(x\) 上的值加 \(-1\)。modify(1,1,n,x,-1); - 查询 \(x\) 的排名
就是看 \([-\infty,x-1]\) 位置上的值的和，在树上递归。
若 \(x>mid\) 则将左儿子的答案加上并递归右儿子；反之递归左儿子。int query_rk(int now,int l,int r,int x){ if(l==r) return 1; int mid=(l+r)>>1; if(x<=mid) return query_rk(lc,l,mid,x); else return tr[lc].val+query_rk(rc,mid+1,r,x); } - 查询排名为 \(x\) 的数
在树上二分。
若 \(x\) 大于左儿子 \([l,mid]\) 的权值 \(v_{lc}\)，则跳转到右儿子 \([mid+1,r]\) 且找区间内排名为 \(x-v_{lc}\) 的数；反之递归左儿子。int query_num(int now,int l,int r,int x){ if(l==r) return l; int mid=(l+r)>>1; if(x<=tr[lc].val) return query_num(lc,l,mid,x); else return query_num(rc,mid+1,r,x-tr[lc].val); } - 查询 \(x\) 的前驱
即查询排名为 \(x\) 的排名 \(-1\) 的数query_sum(1,1,n,query_rk(1,1,n,x)-1); - 查询 \(x\) 的后继
即查询排名为 \(x+1\) 的排名的数（其实查询一个不存在的数的排名会返回小于它的第一个数的最大排名 \(+1\)，其实就等价于大于它的第一个数的排名），就会返回 \(x\) 的后继。query_sum(1,1,n,query_rk(1,1,n,x+1));
动态开点
为后面的线段树合并、可持久化做铺垫。
一开始不建节点，仅一个根节点代表 \([1,n]\)，当出现操作需要访问 \(x\) 时，就建一条链，终点为 \([x,x]\)，注意此时只能再开 \(ch[0/1]\) 代表左右儿子，复杂度仍为 \(O(F(n)\log n)\)。
int cnt; // 线段树上的点数
void modify(int &now,int l,int r,int x,int v){
if(!now) now=++cnt; // 新建节点，加 & 保证不会访问到空节点并直接存在儿子中
if(l==r){
tr[now].val+=v;
return;
}
int mid=(l+r)>>1;
if(x<=mid)
modify(lc,l,mid,x,v);
else
modify(rc,mid+1,x,v);
pushup(now);
}
int query(int &now,int l,int r,int x){
if(!now) now=++cnt;
......
}
线段树合并
很暴力地合并两棵树，暴力合并叶子结点的信息，然后上传。
对于权值线段树更简单，直接把每个位置上的值对应加起来即可，时间复杂度 \(O(n)\)。
int merge(int now1,int now2,int l,int r){
if(!now1) return now2;
if(!now2) return now1;
if(l==r){
tr[now1].val+=tr[now2].val;
return now1;
}
int mid=(l+r)>>1;
tr[now1].ls=merge(tr[now1].ls,tr[now2].ls,l,mid);
tr[now1].rs=merge(tr[now1].rs,tr[now2].rs,mid+1,r);
pushup(now1);
return now1;
}
P4556 [Vani有约会] 雨天的尾巴
有一棵 \(n\) 个节点的树，有 \(m\) 个操作：
- 将 \((u,v)\) 路径上的点的颜色 \(c\) 加 \(1\)。
求操作完后，每个节点最多的颜色是什么，若有数量相同，则取小的。
\(n,c\le 10^5\)
考虑对每个节点建一棵权值线段树，然后树剖维护修改，可以做到 \(O(n\log^2 n)\)，需要动态开点。
由于是离线处理，所以可以在树上差分把区间修改变成单点修改，最后 DFS pushup 一下，每次合并权值线段树，时间复杂度 \(O(n\log n)\)。
code
#include<bits/stdc++.h>
using namespace std;
#define lc tr[now].ls
#define rc tr[now].rs
const int maxn=2e5+3;
const int N=1e5;
struct node{
int ls,rs,val,mx,mxpos;
}tr[maxn<<5];
int cnt;
void pushup(int now){
tr[now].val=tr[lc].val+tr[rc].val;
if(tr[lc].mx>=tr[rc].mx){
tr[now].mx=tr[lc].mx;
tr[now].mxpos=tr[lc].mxpos;
}else{
tr[now].mx=tr[rc].mx;
tr[now].mxpos=tr[rc].mxpos;
}
}
void modify(int &now,int l,int r,int x,int v){
if(!now) now=++cnt;
if(l==r){
tr[now].val+=v;
tr[now].mx=tr[now].val;
tr[now].mxpos=(tr[now].mx?l:0);
return;
}
int mid=(l+r)>>1;
if(x<=mid) modify(lc,l,mid,x,v);
else modify(rc,mid+1,r,x,v);
pushup(now);
}
int merge(int now1,int now2,int l,int r){
if(!now1) return now2;
if(!now2) return now1;
if(l==r){
tr[now1].val+=tr[now2].val;
tr[now1].mx=tr[now1].val;
tr[now1].mxpos=(tr[now1].mx?l:0);
return now1;
}
int mid=(l+r)>>1;
tr[now1].ls=merge(tr[now1].ls,tr[now2].ls,l,mid);
tr[now1].rs=merge(tr[now1].rs,tr[now2].rs,mid+1,r);
pushup(now1);
return now1;
}
int n,m;
int head[maxn]; // 每棵线段树根节点
vector<int>e[maxn];
int dep[maxn],fa[maxn][21];
void dfs1(int u,int Fa){
fa[u][0]=Fa;
dep[u]=(u==1?1:dep[Fa]+1);
for(int v:e[u])
if(v!=Fa)
dfs1(v,u);
}
void init(){
dfs1(1,0);
for(int i=1;i<19;i++){
for(int j=1;j<=n;j++){
int Fa=fa[j][i-1];
if(~Fa) fa[j][i]=fa[Fa][i-1];
else fa[j][i]=Fa;
}
}
}
int lca(int u,int v){
if(dep[u]>dep[v]) swap(u,v);
for(int i=0;i<19;i++)
if((dep[v]-dep[u])>>i&1) v=fa[v][i];
if(u==v) return u;
for(int i=18;~i;i--)
if(fa[u][i]!=fa[v][i])
u=fa[u][i], v=fa[v][i];
return fa[u][0];
}
void dfs(int u,int fa){
for(int v:e[u])
if(v!=fa){
dfs(v,u);
head[u]=merge(head[u],head[v],1,N);
}
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
head[i]=++cnt;
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
e[u].emplace_back(v);
e[v].emplace_back(u);
}
init();
for(int i=1,u,v,c;i<=m;i++){
cin>>u>>v>>c;
int w=lca(u,v);
modify(head[fa[w][0]],1,N,c,-1);
modify(head[w],1,N,c,-1);
modify(head[u],1,N,c,1);
modify(head[v],1,N,c,1);
}
dfs(1,0);
for(int i=1;i<=n;i++)
cout<<tr[head[i]].mxpos<<'\n';
return 0;
}