poj2104：K-th Number

思路：可持久化线段树，利用权值线段树，把建树过程看成插入，插入第i个元素就在第i-1棵树的基础上新建结点然后得到第i棵树，那么询问区间[l,r]就是第r棵树上的信息对应减去第l-1棵树上的信息，然后再利用权值线段树的职能找第k大，这里就巧妙地利用了可持久化线段树不修改原来线段树上的信息而是新建结点来更新信息，这样要询问某次操作下的线段树就访问那次操作新建的root就好了，而这里的区间[l,r]就被转换成了第l次操作到第r次操作，就用第r棵线段树上的信息对应减去第l-1棵线段树上的信息就好了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

#define maxn 100005

int n,q;

int a[maxn];

inline int read(){

	int x=0,f=1;char ch=getchar();

	for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;

	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';

	return x*f;

}

struct node{

	int val,id;

}v[maxn];

bool operator <(node a,node b){return a.val<b.val;}

bool cmp(node a,node b){return a.id<b.id;}

struct functional_segment_tree{

	int treedeg,root[maxn];

	struct treenode{

		int sum,ls,rs;

	}tree[80*maxn];

	void build(int &p,int l,int r){

		if (!p) p=++treedeg;

		if (l==r) return;

		int mid=(l+r)>>1;

		build(tree[p].ls,l,mid),build(tree[p].rs,mid+1,r);

	}

	void change(int &p,int k,int l,int r,int pos){

		tree[p=++treedeg].ls=tree[k].ls,tree[p].rs=tree[k].rs,tree[p].sum=tree[k].sum+1;

		if (l==r) return;

		int mid=(l+r)>>1;

		if (pos<=mid) change(tree[p].ls,tree[k].ls,l,mid,pos);

		else change(tree[p].rs,tree[k].rs,mid+1,r,pos);

	}

	int query(int p,int k,int l,int r,int rank){

		if (l==r) return l;

		int mid=(l+r)>>1,sum=tree[tree[p].ls].sum-tree[tree[k].ls].sum;

		if (rank<=sum) return query(tree[p].ls,tree[k].ls,l,mid,rank);

		else return query(tree[p].rs,tree[k].rs,mid+1,r,rank-sum);

	}

}T;

int main(){

	n=read(),q=read();

	for (int i=1;i<=n;i++) a[i]=read(),v[i].val=a[i],v[i].id=i;

	sort(v+1,v+n+1),sort(a+1,a+n+1);

	for (int i=1;i<=n;i++) v[i].val=i;

	sort(v+1,v+n+1,cmp);

	T.build(T.root[0],1,n);

	for (int i=1;i<=n;i++) T.change(T.root[i],T.root[i-1],1,n,v[i].val);

	while (q--){

		int l=read(),r=read(),k=read();

		printf("%d\n",a[T.query(T.root[r],T.root[l-1],1,n,k)]);

	}

	return 0;

}

巴特西

poj2104：K-th Number

最新文章

热门文章