POJ 2104 可持久化线段树 求区间第k大

Description

Input

Output

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

可持久化线段树厉害之处就是在于它可以利用跟前缀和差不多的思想，把所有区间询问全都变成“从头到尾”的，只要我们这么考虑：一开始有一个空线段树，然后把a[1]加进去，a[2]加进去…… 注意加的时候你不要直接改，而是【弄一棵新线段树】，这样我们就有了n+1棵线段树，当询问l~r的时候，只需要把 线段树[r]所有节点的sum值 减去 线段树[l-1]所有节点的sum值，我们就有了一棵建在[l,r]上的线段树，充分利用历史版本，在历史版本的基础上进行修改。慢慢理解~~

代码：

/* ***********************************************
Author :rabbit
Created Time :2014/4/11 9:19:47
File Name :5.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
struct NODE{
	int l,r,sum;
}node[3000000];
int p_node,m,n,a[100100],root[100100],num[100100],p_num;
void build(int s,int e,int &p){
	p=++p_node;
	node[p].l=node[p].r=node[p].sum=0;
	if(s>=e)return;
	int mid=(s+e)/2;
	build(s,mid,node[p].l);
	build(mid+1,e,node[p].r);
}
void update(int pre,int &p,int s,int e,int mir){
	p=++p_node;
	node[p]=node[pre];
	node[p].sum++;
	if(s>=e)return;
	int mid=(s+e)/2;
	if(mir<=mid)update(node[pre].l,node[p].l,s,mid,mir);
	else update(node[pre].r,node[p].r,mid+1,e,mir);
}
int ask(int r1,int r2,int s,int e,int k){
	if(s>=e)return s;
	int mid=(s+e)/2;
	int left_sum=node[node[r2].l].sum-node[node[r1].l].sum;
	if(left_sum>=k)return ask(node[r1].l,node[r2].l,s,mid,k);
	else ask(node[r1].r,node[r2].r,mid+1,e,k-left_sum);
}
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     while(~scanf("%d%d",&n,&m)){
		 p_node=0;p_num=0;
		 for(int i=1;i<=n;i++){
			 scanf("%d",&a[i]);
			 num[i]=a[i];
		 }
		 sort(num+1,num+n+1);
		 p_num=unique(num+1,num+n+1)-num-1;
		 build(1,p_num,root[0]);
		 for(int i=1;i<=n;i++){
			 int mir=lower_bound(num+1,num+n+1,a[i])-num;
			 update(root[i-1],root[i],1,p_num,mir);
		 }
		 for(int i=1;i<=m;i++){
			 int s,e,k;
			 scanf("%d%d%d",&s,&e,&k);
			 int ans=ask(root[s-1],root[e],1,p_num,k);
			 cout<<num[ans]<<endl;
		 }
	 }
     return 0;
}

POJ 2104 可持久化线段树 求区间第k大,布布扣,bubuko.com

POJ 2104 可持久化线段树 求区间第k大

原文：http://blog.csdn.net/xianxingwuguan1/article/details/23425831