专辑：主席树
文章目录
一个问题
前言
我惊呆了！这竟然只算一个“模板” Q w Q QwQ QwQ（我太弱了？）。正常的主席树模板应该是求序列前缀的第 k k k大（小）数，而不是区间的。所以我们进入这个题之前先看看主席树正常怎么做。
与可持久化线段树的区别
请千万不要把这两个概念搞混了！虽然主席树的名字是乱起的，但是它是“基于权值线段树的可持久化线段树”，而并不是纯粹的可持久化线段树。主席树可以解决的问题都是关于求可持久化的排名（和平衡树有些相似），但是可持久化线段树仅仅做到了“可持久化”的要求。
线段树上第 k k k小
回到主席树，先想想求前缀中的第
k
k
k小该如何去做。我们先想一想平衡树求第
k
k
k大是如何做的。它其实就是一个二分查找树，左边都是更小的，右边都是比它大的。设左子树大小为
s
i
z
l
sizl
sizl，如果
k
<
s
i
z
l
k<sizl
k<sizl，那么它就一定在左子树，否则就是自己或右子树的第
k
−
s
i
z
l
−
1
k-sizl-1
k−sizl−1小（别忘了去掉自己）。那我们尝试把这个方法放在线段树上。但是线段树是按下标排序的，可我们需要按大小排序才能行。于是我们又引出一种线段树：权值线段树
权值线段树十分特别，它的点存的是某个值域内有几个数，所以它是有序的，于是我们就可以依葫芦画瓢，按平衡树的方法来找第
k
k
k小了。
深度的思考
权值线段树本来是用来找第
k
k
k小的，但是本题有一个很变态的要求：要求的是某个前缀中的第
k
k
k小！我们可以思考一下，如果已经加到了第
i
i
i个数，那么此时前
i
i
i个数都已经加到权值线段树里了，刚好就是我们要求的某一个前缀！所以我们只需要让线段树可持久化就行了。
先看一个问题：
洛谷P3949
我们知道，线段树不是一个可持久化数据结构，但是这个题竟然要求我们访问之前的版本！
很容易想出一个方案：每次新开一个线段树存储。但是很明显
M
L
E
MLE
MLE。
我们来画个图思考一下：
假如我们更改了结点
8
8
8后，不难发现只有结点
8
,
4
,
2
,
1
8,4,2,1
8,4,2,1需要修改。所以我们修改之后只需要新建这几个结点就可以保存新旧两个版本了，其余没修改的地方直接向旧版本的结点连边即可。
于是，每次修改只需要新开
log
n
\log n
logn的结点，过掉这个题完全没有问题。
回到原题
我们知道了主席树怎么做，现在就是解决这个问题：区间中的第
k
k
k小。首先，我们的主席树可以得到前缀的第
k
k
k小，然后要求的是某个区间，于是我们自然而然地想到了前缀和数组是怎么求某个区间的和的：
s
[
r
]
−
s
[
l
−
1
]
s[r]-s[l-1]
s[r]−s[l−1]。于是我们直接用
r
r
r版本的线段树减去
l
−
1
l-1
l−1版本的线段树的权值即可。但是如何把两个线段树放在一起处理呢？我们又引出一个模型：合并线段树。
其实合并线段树并不难，就是从两个线段树的根出发，一起往左合并一下，再一起往右合并一下。因为本题虽然是不同的线段树，但是它们是同构的，所以不需要考虑某个地方只有一个点的情况。注意，本题的
a
a
a很大，用权值当下标需要离散化或
m
a
p
map
map，但是
m
a
p
map
map常数太高，会
T
L
E
TLE
TLE。
原题代码
#include<bits/stdc++.h>
using namespace std;
const int NN=2e5+4;
int a[NN],b[NN];
struct segtree
{
int sum,lson,rson;
}tr[NN*20];
int idx,t[NN];
int build(int l,int r)
{
int point=++idx;
if(l==r)
return idx;
int mid=l+(r-l)/2;
tr[point].lson=build(l,mid);
tr[point].rson=build(mid+1,r);
return point;
}
int update(int u,int l,int r,int id)
{
int point=++idx;
tr[point]=tr[u];
if(l==r)
{
tr[point].sum++;
return point;
}
int mid=l+(r-l)/2;
if(id<=mid)
tr[point].lson=update(tr[u].lson,l,mid,id);
else
tr[point].rson=update(tr[u].rson,mid+1,r,id);
tr[point].sum=tr[tr[point].lson].sum+tr[tr[point].rson].sum;
return point;
}
int query(int u,int v,int l,int r,int k)
{
if(l==r)
return l;
int mid=l+(r-l)/2;
if(tr[tr[v].lson].sum-tr[tr[u].lson].sum>=k)
return query(tr[u].lson,tr[v].lson,l,mid,k);
else
return query(tr[u].rson,tr[v].rson,mid+1,r,k-tr[tr[v].lson].sum+tr[tr[u].lson].sum);
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
memcpy(b,a,sizeof(a));
sort(b+1,b+1+n);
int cnt=unique(b+1,b+1+n)-b-1;
t[0]=build(1,cnt);
for(int i=1;i<=n;i++)
t[i]=update(t[i-1],1,cnt,lower_bound(b+1,b+1+cnt,a[i])-b);
while(m--)
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",b[query(t[l-1],t[r],1,cnt,k)]);
}
return 0;
}