权值线段树
线段树在这里作为前置知识，我们就不说了，而且权值线段树也不是核心内容，不会大篇幅讲。
首先，权值线段树在维护什么？维护的是桶。
然后，权值线段树有什么用？可以求一些序列的第 \(k\) 大之类的问题。
于是我们放个板子题。
第 k 小整数
简单题，直接看代码和注释就行，当然也可以使用线性的快速选择算法。
事实上，权值线段树左，右边界为 \([l,r]\) 的节点在这里维护的是区间 \([l,r]\) 内的数的个数（但是要去重）。
代码：
#include<bits/stdc++.h>
#define int long long
#define N 300005
using namespace std;
int n,k,a[N],tr[N<<2];
void pushup(int u){
tr[u]=tr[u<<1]+tr[u<<1|1];
}
void build(int u,int l,int r){
if(l==r){
tr[u]=a[l];//大小为这个元素的桶
return;
}
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
int qry(int u,int l,int r,int k){
if(l==r)return l;
int mid=l+r>>1;
if(tr[u<<1]>=k)return qry(u<<1,l,mid,k);//如果左子树总个数更大，那么答案在左子树里
else return qry(u<<1|1,mid+1,r,k-tr[u<<1]);//否则在右子树里，但是我们需要减掉左子树的大小
}
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
int x;
cin>>x;
if(a[x]==0)a[x]++;//这里多个看成一个，所以只统计一次
}
a[30000]++;//放一下哨兵
build(1,1,30000);
int res=qry(1,1,30000,k);
if(res==30000)cout<<"NO RESULT";
else cout<<res;
return 0;
}
线段树合并
基础概念没啥好说的，就是合并两颗线段树。所以直接看题。
Promotion Counting P
一道裸题。显然权值数量可以合并，所以我们对每个点建立一颗权值线段树，然后跑一遍 \(dfs\)，在回溯的时候合并和求答案。
然后我们怎么求答案？显然地，我们查一下权值线段树中权值比他大的数的数量就行了。
直接看代码：
#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;
int n,p[N],a[N],res[N],rt[N];
int h[N],e[N],ne[N],idx,cnt;
struct node{
int l,r,sum;
}tr[N<<4];
void add(int a,int b){
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void modify(int &u,int l,int r,int x){
if(l>r)return;
u=++cnt;//动态开点
if(l==r){
tr[u].sum++;
return;
}
int mid=l+r>>1;
if(x<=mid)modify(tr[u].l,l,mid,x);//如果在左区间里，插入到左子树
else modify(tr[u].r,mid+1,r,x);//否则插入到右子树
tr[u].sum=tr[tr[u].l].sum+tr[tr[u].r].sum;//数量就是两边加起来
}
int qry(int u,int l,int r,int x){
if(!u)return 0;
if(l>=x)return tr[u].sum;//如果区间内最小数已经不小于目标值，返回数量
int res=0;
int mid=l+r>>1;
if(mid>=x)res+=qry(tr[u].l,l,mid,x);//如果左子树里面的数可能比目标值大就递归
res+=qry(tr[u].r,mid+1,r,x);
return res;
}
int merge(int x,int y){
if(!x||!y)return x+y;//返回非空的一边
tr[x].l=merge(tr[x].l,tr[y].l);
tr[x].r=merge(tr[x].r,tr[y].r);//合并两棵树
tr[x].sum=tr[tr[x].l].sum+tr[tr[x].r].sum;//数量合并同上
return x;
}
void dfs(int u){
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
dfs(j);
rt[u]=merge(rt[u],rt[j]);//在dfs时合并
}
res[u]=qry(rt[u],1,n,a[u]+1);//查询比这个数大的数的数量
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>p[i];
a[i]=p[i];
}
sort(p+1,p+n+1);
int len=unique(p+1,p+n+1)-p-1;
for(int i=1;i<=n;i++){
a[i]=lower_bound(p+1,p+len+1,a[i])-p;//离散化
}
memset(h,-1,sizeof h);
for(int i=2;i<=n;i++){
int x;
cin>>x;
add(x,i);
}
for(int i=1;i<=n;i++){
modify(rt[i],1,n,a[i]);//先把每个数开一颗权值线段树
}
dfs(1);
for(int i=1;i<=n;i++){
cout<<res[i]<<'\n';
}
return 0;
}