浅尝主席树
世界上真的有。。。CS
众所周知
线段树是一种非常强大的静态区间数据结构，它有着优秀的对数级时间复杂度，可以快速地解决包含结合律的信息处理。
举个栗子，区间和，区间最值，这些都是可以由两个相邻不相交的小区间合并而来。
但是，如果我说，
前置芝士，不懂就问
二分
权值线段树的强大在于它具有单调性，二分可以解决很多与值域相关的问题
离散化
离散化是对于缩小值域，减小空间开销来说十分必要。
线段树
（不是你连线段树都不会还学什么主席树？）
动态开点
主席树必须使用动态开点，否则会有极其恐怖的空间开销（详见后文）。
下面引入
假设你有一段长度为
- 给出形如
l r k的三元组，查询序列a_l 到a_r 中第k 小的数，并输出。
聪明的你立刻想到，要是自己学过
但是你不是十分的聪明，所以你只能另寻他法。
好在你的同学HZX十分的聪明，他告诉你，这道题可以用权值线段树来解决。
所以，权值是什么？
权值，就是指一个值，在序列中出现的次数。
比如说下面这个序列：
1 1 4 5 1 4
其中1的权值就是3，4的权值是2，5的权值是1。
那么，权值线段树又是什么？？
想想我们平时打的线段树，都是在原序列的基础上建立的。
而权值线段树，就是在原数组的权值数组上建立的。
以上面的序列为例，我们来建立一棵权值线段树。
首先，先把这个序列的权值数组求出来
3 0 0 2 1 0
（下标从 1 开始）
然后对着这个数组建立线段树即可（建树方法与普通线段树相同）。
细心的同学或许发现了，权值数组其实只和原数组的数值大小有关，也就是说，
不理解可以自己看上面的两个序列自己推。
这个东西，我们通常叫做
道理我都懂，可是怎么做呢？
很简单，我们考虑这样一种思路：将原序列的前缀（从1到1，从1到2 。。。从1到n），分别看做是一个序列，对于它们（前缀数组）分别建立权值线段树，也就是说，我们一共要建
嗯。。。
那又有什么用？
有的兄弟，有的。
我们不难发现，每棵权值线段树的形态都是一样的，虽然我们会将部分点省略，可是从存储的角度来说，它们都是一样的。
这意味着什么？
意味着不同的两棵线段树的相对应的节点之间可以做减法，当然，是它们存储的值做减法。
将在线段树上做减法简化一下，我们把它放到一段权值序列上。
2 0 0 1 0 0
这是第3棵权值线段树对应的权值数组[1,1,4]
3 0 0 1 1 0
这是第5棵权值线段树对应的权值数组[1,1,4,5,1]
如果我们把后者的每一个值都减去前者对应的值，那么恭喜你，得到了一个新的权值数组：
1 0 0 0 1 0
这是什么，仔细观察，发现它恰好与[5,1]这个序列的权值数组相同，如果自己多尝试几次，就会得出一个结论：
[1,R] 的权值数组与 [1,L] 的权值数组之间的差
就等于[L+1,R] 的权值数组
巧了，既然权值数组可以做减法，权值线段树也可以做减法，那么两者的含义是否相同？
相同的
所以我们只需要将第
这其实省了很多事，我们只需要
问题来了，我知道这个又有什么用？
先别急，我的思路还没讲完。
假设我们有了一棵权值线段树，表示
什么，你问我怎么配凑？
方法如下：
先看左半边的数的个数（因为是权值数组，所以数值越靠左，数值就越小，比
看到了这个二分，那么其实只要每次递归询问即可（有个小细节，如果值在左区间，查询的
单次的时间复杂度为对数级，时间性能十分优越。
但是问题又来了
你开
难道，我们就要放弃这样一种时间非常优越的算法了吗？
实则不然，一个叫黄嘉泰的神犇在考场上仔细琢磨，发现前一棵权值线段树和后一棵权值线段树之间，有大量的节点信息是重复的。
具体来说，第
所以我们并不需要真的将那些没有变化的节点建出来占用空间，只需要让当前节点的其中一个子节点（左或右，视情况而定）指向前一棵权值线段树的对应节点就可以了。
不过这样一来就不能用普通线段树的
这样一来，每次修改操作会导致
那么其实这道题已经做完了。
Talk is CHEAP ,Show you my Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define V vector
const int INF=1e9+10,N=2e5+10;
int root[N],tot=0;
struct node{
int ls,rs,w;
}a[N*30];//动态开点，空间要预留好
void build(int &x,int l,int r){//建一棵0的空树，有的题不建会RE
x=++tot;
if(l==r) return;
int mid=l+r>>1;
build(a[x].ls,l,mid);
build(a[x].rs,mid+1,r);
}
int update(int pos,int last,int l,int r,int w){//修改点，借用的上一棵线段树的点，覆盖的区间，加的值
int x=++tot;
a[x]=a[last];
a[x].w+=w;
if(l==r) return x;
int mid=l+r>>1;
if(pos<=mid) a[x].ls=update(pos,a[x].ls,l,mid,w);
else a[x].rs=update(pos,a[x].rs,mid+1,r,w);
return x;
}
int query(int L,int R,int l,int r,int k){
if(l==r) return l;
int mid=l+r>>1,lk=a[a[R].ls].w-a[a[L].ls].w;
if(lk>=k) return query(a[L].ls,a[R].ls,l,mid,k);
else return query(a[L].rs,a[R].rs,mid+1,r,k-lk);
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,q;cin>>n>>q;
V<int>a(n+1),b,c(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
b=a;
sort(b.begin()+1,b.end());
int nn=unique(b.begin()+1,b.end())-b.begin()-1;
for(int i=1;i<=n;i++) c[i]=lower_bound(b.begin()+1,b.begin()+1+nn,a[i])-b.begin();//数据过大，要离散化
build(root[0],1,nn);
for(int i=1;i<=n;i++) root[i]=update(c[i],root[i-1],1,nn,1);
while(q--){
int l,r,k;cin>>l>>r>>k;
cout<<b[query(root[l-1],root[r],1,nn,k)]<<"\n";
}
return 0;
}如果你不是很理解上面的代码，可以自己用AI去问，也可以学习其他常熟更为优秀的代码。
好了，你已经学会了主席树了，现在要给你上点强度了
放心，很简单的。
例题
看过题了，想想怎么打？
暴力：这肯定会
那我们就直接想怎么用主席树。
怎么想到用主席树的呢？因为这是一道十分经典的二维偏序问题。
什么是二维偏序？
你可以大致理解为对于同一个变量