题意
给一组数，问某个区间第K小的数
题解
主席树模板题，网上有很多关于主席树的讲解。主席树的话，我的理解就是类似于GIT的一种重复利用上一次结果的数据结构，很有意思。每插入一个点就建立一个线段树，这样的话可以大大提升线段树的能力，使得普通线段树具有部分平衡树的功能。当然，如果暴力去建的话，时间和空间都是不允许的，但是有神牛想出了主席树，大大简化了建树的时间和空间。节省时间和空间的方法是每次更新只更新真正要更新的点，不是真正要更新的点就可以用上一次的值，这样可以大大简化时间和空间复杂度。（如果还不理解的话，用一下GIT这个版本控制工具就理解了） 应用到本道题，我们可以先排个序，将下标离散化处理一下（事实上就是给每一个点分配一个唯一的rank值，代表这个值的大小位置）。然后就可以将点一个个插入到线段树中间。最后查询的时候，查询这个区间的历史更新记录就可以知道更新了哪几个点。这些点对应排序后的数下标。查找第K个值是以一种二分的思想进行查找，比如说左子节点有a个，而K>a，那么答案一定在右子节点中，去右子节点中继续二分去搜就可以了。最后把二分搜索的坐标对应的值输出就可以了。
代码
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<bitset>
#include<stack>
#include<string>
#define UP(i,l,h) for(int i=l;i<h;i++)
#define DOWN(i,h,l) for(int i=h-1;i>=l;i--)
#define W(a) while(a)
#define MEM(a,b) memset(a,b,sizeof(a))
#define LL long long
#define INF 0x3f3f3f3f3f3f3f3f
#define MAXN 100010
#define MOD 1000000007
#define EPS 1e-3
using namespace std;
const int NN=MAXN*
25;
struct Node {
int val,x;
bool operator < (
const Node b)
const{
return val<b.val;
}
};
Node nodes[MAXN];
int xrank[MAXN],root[MAXN];
int sum[NN],ln[NN],rn[NN];
int tot;
void maintain(
int k){
sum[k]=sum[ln[k]]+sum[rn[k]];
}
int update(
int o,
int L,
int l,
int r){
int k=++tot;
sum[k]=sum[o];
ln[k]=ln[o];
rn[k]=rn[o];
if(L==l&&r==l){
sum[k]++;
return k;
}
int m=(l+r)/
2;
if(L<=m) ln[k]=update(ln[o],L,l,m);
else rn[k]=update(rn[o],L,m+
1,r);
maintain(k);
return k;
}
int query(
int a,
int b,
int L,
int l,
int r){
if(l==r)
return l;
int m=(l+r)/
2;
int tmp=sum[ln[b]]-sum[ln[a]];
if(L<=tmp)
return query(ln[a],ln[b],L,l,m);
return query(rn[a],rn[b],L-tmp,m+
1,r);
}
int main() {
int n,m;
W(~
scanf(
"%d%d",&n,&m)) {
tot=
0;
UP(i,
1,n+
1){
scanf(
"%d",&nodes[i].val);
nodes[i].x=i;
}
sort(nodes+
1,nodes+n+
1);
UP(i,
1,n+
1){
xrank[nodes[i].x]=i;
}
root[
0]=
0,ln[
0]=
0,rn[
0]=
0,sum[
0]=
0;
UP(i,
1,n+
1){
root[i]=update(root[i-
1],xrank[i],
1,n);
}
W(m--){
int x,y,c;
scanf(
"%d%d%d",&x,&y,&c);
printf(
"%d\n",nodes[query(root[x-
1],root[y],c,
1,n)].val);
}
}
}
