[poj2104]区间第k大值

发表于 2017-07-30   |   分类于 未分类  |  访问: 53 次

题意:不断的求某个区间第k大值
做法:主席树,先离散化一下数字,然后建立一棵以数值大小为基准的线段树

一个无聊的下午结合以前看过的一些资料自己YY出了这种玄学操作,还蛮有趣的

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int _maxn=100008;
int tot,g[_maxn],n,m,mapx[_maxn];
int getint(){
	int ans=0;
	char ch=getchar();
	while(ch<'0' || ch>'9')	ch=getchar();
	while(ch>='0' && ch<='9'){
		ans=ans*10+ch-'0';
		ch=getchar();
	}
	return ans;
}
struct e{
	int num,xu,mapnum;
}a[_maxn];
struct e1{
	int l,r,sum,num;
	e1(){num=0;}
}tree[_maxn*20];
bool cmp1(e p1,e p2){return p1.num<p2.num;}
bool cmp2(e p1,e p2){return p1.xu<p2.xu;}
void build(int p,int l,int r){
	if(l==r)	return;
	int mid=(l+r)>>1;
	build(tree[p].l=++tot,l,mid);
	build(tree[p].r=++tot,mid+1,r);
}
int push(int p,int l,int r,int keyy){
	if(l==r){
		tree[++tot].sum=1;
		tree[tot].num=keyy;
		return tot;
	}
	int mid=(l+r)>>1,newp=++tot;
	tree[newp]=tree[p];
	if(keyy>mid)
		tree[newp].r=push(tree[p].r,mid+1,r,keyy);
	else
		tree[newp].l=push(tree[p].l,l,mid,keyy);
	tree[newp].sum=tree[tree[newp].l].sum+tree[tree[newp].r].sum;
	return newp;
}
int query(int ltr,int rtr,int kth){
	if(tree[rtr].num!=0)	return tree[rtr].num;
	if(tree[tree[rtr].l].sum-tree[tree[ltr].l].sum>=kth)
		return query(tree[ltr].l,tree[rtr].l,kth);
	else
		return query(tree[ltr].r,tree[rtr].r,kth-(tree[tree[rtr].l].sum-tree[tree[ltr].l].sum));
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].num);
		a[i].xu=i;
	}
	sort(a+1,a+n+1,cmp1);
	for(int i=1;i<=n;i++){
		a[i].mapnum=i;
		mapx[i]=a[i].num;
	}
	sort(a+1,a+n+1,cmp2);
	build(g[0]=++tot,1,n);
	for(int i=1;i<=n;i++)
		g[i]=push(g[i-1],1,n,a[i].mapnum);
	int l,r,kth;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&l,&r,&kth);
		printf("%d\n",mapx[query(g[l-1],g[r],kth)]);
	}
	return 0;
}

发表新评论

© 2017 Powered by Typecho & Theme Quark