POJ 2104 K-th Number （可持久化线段树）

题目大意

给一个长度为n的序列，有m个询问，每次询问一个区间里面第k小的数。

解题分析

静态的区间第k大。复习了一下可持久化线段树。

首先对数值离散化，建一颗权值线段树。按照序列的顺序依次插入，每一个数对应于一个版本的线段树。

对于每个询问[l,r]，在第r个版本的线段树和第l个版本的线段树之间进行查询。

本质上来说，可持久化线段树干了一件前缀和的事情，每棵线段树记录了1~i序列的权值信息。

参考程序

#include <cstdio>

#include <algorithm>

using namespace std;

const int N=100008;

int a[N],x[N],rt[N],ls[N*20],rs[N*20],sum[N*20];

int tot,n,m;

void build(int l,int r,int &rt)

{

	rt=++tot;

	sum[rt]=0;

	if (l==r) return;

	int m=l+r>>1;

	build(l,m,ls[rt]);

	build(m+1,r,rs[rt]);

}

void insert(int val,int l,int r,int &rt,int last)

{

	rt=++tot;

	ls[rt]=ls[last]; rs[rt]=rs[last]; sum[rt]=sum[last]+1;

	if (l==r) return;

	int m=l+r>>1;

	if (val<=m) insert(val,l,m,ls[rt],ls[last]);

	else insert(val,m+1,r,rs[rt],rs[last]);

}

int query(int k,int l,int r,int L,int R)

{

	if (l==r) return x[l];

	int m=l+r>>1;

	if (sum[ls[R]]-sum[ls[L]]>=k) return query(k,l,m,ls[L],ls[R]);

	else return query(k-(sum[ls[R]]-sum[ls[L]]),m+1,r,rs[L],rs[R]);

}

int main()

{

	scanf("%d%d",&n,&m);

	for (int i=1;i<=n;i++) {scanf("%d",&a[i]);x[i]=a[i];}

	sort(x+1,x+n+1);

	int nn=unique(x+1,x+n+1)-x-1;

	build(1,nn,rt[0]);

	for (int i=1;i<=n;i++)

	{

		int y=lower_bound(x+1,x+nn+1,a[i])-x;

		insert(y,1,nn,rt[i],rt[i-1]);

	}

	for (int i=1;i<=m;i++)

	{

		int l,r,k;

		scanf("%d%d%d",&l,&r,&k);

		printf("%d\n",query(k,1,nn,rt[l-1],rt[r]));

	}

}

巴特西

POJ 2104 K-th Number （可持久化线段树）

题目大意

解题分析

参考程序

最新文章

热门文章