可持久化线段树
也叫函数式线段树也叫主席树,其主要思想是充分利用历史信息,共用空间
http://blog.sina.com.cn/s/blog_4a0c4e5d0101c8fr.html
这个博客总结的挺好的!
区间k大数问题
对于没有修改的版本,我们可以先离散化然后对权值建树。
结点存储的是该权值范围内出现元素的总次数。
在线段树上找k大数时就像平衡树询问k大数一样根据结点上的信息往左或者往右走。
现在可以利用函数式线段树维护权值出现数量,将数列中每个结点依次插入线段树,
第r次插入后的线段树与第l-1次插入的线段树之“差”(对应结点的值相减,因为按权值建树结构是一样的)得到的线段树里进行上述的查找k大数操作即可。
总之,对于点操作,新增加一个点或修改一个点,只要新建一条从这个点到root[i]的路径即可,这样就形成第i个历史版本的线段树
模板引自http://blog.csdn.net/crazy_ac/article/details/8033596
// File Name: 2104.cpp
// Author: Zlbing
// Created Time: 2013年10月06日 星期日 18时04分39秒 #include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,r,n) for(int i=r;i<=n;i++)
#define RREP(i,n,r) for(int i=n;i>=r;i--)
const int MAXN=1e5+;
int ls[MAXN*],rs[MAXN*];
int sum[MAXN*];
int root[MAXN];
//root表示N颗线段树的根结点
int tot;
void build(int l,int r,int& rt)
{
rt=++tot;
sum[rt]=;
if(l==r)return;
int m=(l+r)>>;
build(l,m,ls[rt]);
build(m+,r,rs[rt]);
}
void update(int last,int p,int l,int r,int &rt)
{
rt=++tot;
ls[rt]=ls[last];
rs[rt]=rs[last];
sum[rt]=sum[last]+;
if(l==r)return;
int m=(l+r)>>;
if(p<=m)update(ls[last],p,l,m,ls[rt]);
else update(rs[last],p,m+,r,rs[rt]);
}
int query(int ss,int tt,int l,int r,int k)
{
if(l==r)return l;
int m=(l+r)>>;
int cnt=sum[ls[tt]]-sum[ls[ss]];
if(k<=cnt)
return query(ls[ss],ls[tt],l,m,k);
else
return query(rs[ss],rs[tt],m+,r,k-cnt);
}
int num[MAXN],hash[MAXN];
int main()
{
int n,m;
int cas;
scanf("%d",&cas);
while(cas--)
{
scanf("%d%d",&n,&m);
REP(i,,n)
{
scanf("%d",&num[i]);
hash[i]=num[i];
}
tot=;
sort(hash+,hash+n+);
int cnt=unique(hash+,hash+n+)-hash-;
build(,cnt,root[]);
REP(i,,n)
{
num[i]=lower_bound(hash+,hash+cnt+,num[i])-hash;
}
REP(i,,n)
{
update(root[i-],num[i],,cnt,root[i]);
}
int a,b,c;
REP(i,,m)
{
scanf("%d%d%d",&a,&b,&c);
int ans=query(root[a-],root[b],,cnt,c);
printf("%d\n",hash[ans]);
}
}
return ;
}