poj 2104 (可持久线段树/主席树 区间第k大)

K-th Number

Time Limit: 20000MS		Memory Limit: 65536K
Total Submissions: 71836		Accepted: 25581
Case Time Limit: 2000MS

Description

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment. 
That is, given an array a[1...n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: "What would be the k-th number in a[i...j] segment, if this segment was sorted?" 
For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2...5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.

Input

The first line of the input file contains n --- the size of the array, and m --- the number of questions to answer (1 <= n <= 100 000, 1 <= m <= 5 000). 
The second line contains n different integer numbers not exceeding 109 by their absolute values --- the array for which the answers should be given. 
The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k).

Output

For each question output the answer to it --- the k-th number in sorted a[i...j] segment.

Sample Input

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

Sample Output

5
6
3

Hint

This problem has huge input,so please use c-style input(scanf,printf),or you may got time limit exceed.

 

主要思想：主席树是利用函数式的编程思想使得线段树支持查询历史版本，同时充分利用他们之间的共同数据来减少时间和内存消耗的数据结构（这些东西不理解没什么关系，到最后慢慢就懂了）一棵线段树的节点维护的是当前节点对应的区间信息，若每次区间不同则处理较为困难，，例如频繁的询问区间第K大元素（较为简单的思想是根据归并排序思想实现的归并树，但是时空复杂度都较高）

第一部分.静态主席树

发明者的原话：“对于原序列的每一个前缀[1···i]建立出一棵线段树维护值域上每个数出现的次数，则其树是可减的”

可以加减的理由：主席树的每个节点保存的是一颗线段树，维护的区间信息，结构相同，因此具有可加减性（关键）

首先开一个数组t[n]，存储内容为a中排序并去重的值（类似于离散化），每棵线段树维护的内容是a1...ai此区间中的树在t[n]中出现的次数

 

 

 

这是一道可持久化线段树(主席树)的模板题 
主席树的本质是保存几个形态完全相同的历史版本 
那么每加入数组的一位都建出一个船新的版本 
这样的话第i个版本就保存了前i个数的所有信息 
所以说我们需要查询[l,r]的信息只需要将第r个版本-第l-1个版本就好了

那么每棵线段树维护什么信息呢? 
因为要求区间第k小,并且已经能将[l,r]中的点信息提取出来,考虑按大小排序后搞个前缀和查询即可 
那么线段树的叶子节点保存这个叶子节点所对应的数的出现次数,非叶子节点保存左右节点和即可

每次查询当前节点的左儿子大小和k的大小关系即可
 

/*
思考：不管是线段树 还是可持久线段树  树的叶节点个数都是n个（n个数题目给出）
所以在更新或者是查新都可以是  l,r  (l+r)>>1  if(l==r){找到叶节点} 
*/ 


#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;
const int N=1e5+10;
struct node
{
	int l,r,sum;
}tree[N*20];
int root[N],s[N];
vector<int>vec;
int getid(int x)
{
	return lower_bound(vec.begin(),vec.end(),x)-vec.begin()+1;
}
int cnt;
//每一次调用一次 update 就是建立一个线段树 所以这题建立了n课线段树 
//这个线段树每个节点存的是数的出现次数 
void update(int l,int r,int &x,int y,int pos)
{
	x=++cnt;
	tree[x]=tree[y];//这步是为了 把y线段树没有修改给x线段树 
	tree[x].sum++;
	if(l==r) return;
	int mid=(l+r)>>1;
	if(pos<=mid) update(l,mid,tree[x].l,tree[y].l,pos);
	else update(mid+1,r,tree[x].r,tree[y].r,pos); 
}
int query(int l,int r,int x,int y,int k)
{
	if(l==r) return l;
	int mid=(l+r)>>1;
	//则sum= (1~r)树的左节点数字出现的次数 - (1~(l-1))树的左节点数字出现的次数 
    //即sum等于([l,r])树左儿子数字出现的次数 
	int sum=tree[tree[y].l].sum-tree[tree[x].l].sum;
	//当 左儿子数字出现的次数大于等于k时 意味着 第k小的数字在做左子树上 
	if(sum>=k) return query(l,mid,tree[x].l,tree[y].l,k);
	else return query(mid+1,r,tree[x].r,tree[y].r,k-sum);
	//否则去右子树处找地k-sum小的数字 
}
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&s[i]),vec.push_back(s[i]);
	sort(vec.begin(),vec.end());
	vec.erase(unique(vec.begin(),vec.end()),vec.end());
	n=vec.size();//不写这步也可以 
	for(int i=1;i<=n;i++) update(1,n,root[i],root[i-1],getid(s[i]));
	for(int i=1;i<=m;i++){
		int x,y,k;
		scanf("%d %d %d",&x,&y,&k);
		printf("%d\n",vec[query(1,n,root[x-1],root[y],k)-1]);
	}
	return 0;
}