权值线段树

可以参考这篇博客的易懂图解。

数据结构 线段树--权值线段树 详解_HeartFireY的博客-CSDN博客_权值线段树

权值线段树即维护数出现的次数的线段树。区间可设为数的大小，为了减小复杂度，可以离散化。

由于是动态维护，需要像扫描线一样动态开点。

这样的线段树主要用来下求第k大/小的信息。

板子：

/*keep on going and never give up*/
#include
using namespace std;
#define int long long
#define ll long long
#define db(x) cerr<<(#x)<<" "<<(x)<<" "<>1;
	if(x<=mid) add(ls,l,mid,x);
	if(x>mid) add(rs,mid+1,r,x);
	t[p]=t[ls]+t[rs];
}
int ask(int p,int l,int r,int L,int R){
	if(l>=L&&r<=R) return t[p];
	int res=0;
	int mid=l+r>>1;
	if(L<=mid) res+=ask(ls,l,mid,L,R);
	if(R>mid) res+=ask(rs,mid+1,L,R);
	return res;
}
int kth_max(int p,int l,int r,int k){
	if(l==r) return l;
	int mid=l+r>>1;
	if(k<=t[rs]) return kth_max(rs,mid+1,r,k);
	if(k>t[rs]) return kth_max(ls,l,mid,k);
}
int kth_min(int p,int l,int r,int k){
	if(l==r) return l;
	int mid=l+r>>1;
	if(k<=t[ls]) return kth_min(ls,l,mid,k);
	if(k>t[ls]) return kth_min(rs,mid+1,r,k);
}