可持久化线段树---主席树
————恢复内容开始————
主席树
1.问题引入:(来源：shoi2006)
描述
你为Macrohard公司的数据结构部门工作，你的工作是重新写一个数据结构，这个数据结构能快速地找到一段数列中第k大的数。
就是说，给定一个整数数列a[1..n]，其中每个元素都不相同，你的程序要能回答一组格式为Q (i , j , k)的查询，Q(i, j ,k)的意思是“在a[i..j]中第k大的数是多少？”
例如令 a = {1, 5, 2, 6, 3, 7, 4}，查询格式为Q (2 , 5 , 3)，数列段a[2..5] = {5, 2, 6, 3}，第3大的数是5，所以答案是5。
输入
文件第一行包括一个正整数n，代表数列的总长度，还有一个数m，代表有m个查询。 n，m满足：1≤n≤100 000, 1≤m≤5 000 第二行有n个数，代表数列的元素，
所有数都不相同，而且不会超过109 接下来有m行，每行三个整数i , j , k，代表一次查询， i , j , k满足1≤i≤j≤n, 1≤k≤j − i + 1
输出
输出每个查询的答案，用换行符隔开
样例输入
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
样例输出
5
6
3
6
3
看起来好简单滴亚子四不四？？？直接取出取出询问区间进行一遍sort，然后O(1)的复杂度就可以解决了qwq。但是如果出现了这种情况呢？题目会给出多个询问
，每次都询问同一个很长的区间。那我们每次都重新排序吗？时间复杂度怎么说？？那么，为了解决这一类问题，新的算法就诞生了
2，算法流程介绍
我们不妨维护多棵权值线段树，树上的每个结点维护如下几个信息：l：其左儿子的编号，r：其右儿子的编号，sum：表示题目中所给出的序列的前i个(i<=n)元素
在[l,r]内出现的次数，特别的，由于这道题询问的是第k大的数，我们并不关心第k大的数有几个，所以，我们需要进行去重操作
那么我们每次向主席树中插入新元素的时候，一定会更新一条链上的所有节点的sum值，而其他的则完全不用变，那么，我们还需要再建立一棵新的树吗？
其实并不需要（你想建也建不了吖空间只有那么大qwq），我们可以让他跟上一棵树共享一部分数据。
3.上代码咯
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100005<<4
using namespace std;
struct node{
int val;
int l;
int r;
int sum;
node(){
sum=0;
}
};
node tree[ N<<2 ];
struct Node{
int id;
int v;
}Val[N];
int n,m,num[N];
int cnt=0;
int root[N];
int rank[N];//数据离散化之后形成的新的序列
bool cmp(Node a,Node b)
{
return a.v<b.v;
}
inline int Read()
{
int num=0,k=1;
char c=getchar();
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
if(c=='-'){k=-1;c=getchar();}
while(c>='0'&&c<='9'){num=(num<<1)+(num<<3)+(c^48);c=getchar();}
return num*k;
}
inline int build(int l,int r)
{
int t = ++cnt;//当前结点标号
int mid = (l+r) >> 1;
if (l == r) return t;//如果这是一个叶子结点
tree[t].l = build(l, mid);tree[t].r = build(mid+1, r);
}
inline void pre_work()
{
cnt=1;root[0]=0;//现在只有一个结点，滴0棵树的树根是0
tree[0].l=tree[0].r=tree[0].sum=0;
}
inline void update(int num,int &rt,int l,int r)
{
tree[cnt++]=tree[rt];
rt=cnt-1;
tree[rt].sum++;
if(l==r) return ;
int mid = (l + r)>>1 ;
if(num <= mid) update(num, tree[rt].l, l, mid);//要修改的链在左边的话，就共用右边
else update(num, tree[rt].r, mid + 1, r);//同上
}
inline int query(int i, int j, int k, int l, int r)
{
int d = tree[tree[j].l].sum - tree[tree[i].l].sum;
if(l == r) return l;
int mid = (l + r)>>1;
if(k <= d) return query(tree[i].l, tree[j].l, k, l, mid);
else return query(tree[i].r, tree[j].r, k - d, mid + 1, r);
}
int main ()
{
n=Read();m=Read();
for(int i=1;i<=n;i++)
{
Val[i].v=Read();
Val[i].id=i;
}
sort(Val+1,Val+n+1,cmp);
for(int i=1;i<=n;i++) rank[Val[i].id]=i; // 数据离散化
pre_work();
for(int i=1;i<=n;i++)
{
root[i]=root[i-1];
update(rank[i],root[i],1,n);
}
int left, right, k;
for(int i = 1; i <= m; i++)
{
left=Read();right=Read();k=Read();
printf("%d\n", Val[query(root[left - 1], root[right], k, 1, n)].v);
}
return 0;
}
版权声明：本文为Roysblog原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。