POJ 2104 K-th Number

~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

2019寒假集训题

#.K-th Number

题面

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$.

简要翻译

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

Input

第一行包含两个整数$n$,$m$分别代表序列的长度和询问的个数。

第二行包含$n$个整数代表序列。

下面包含$m$行，每行包含三个数$i,j,k$，代表区间$[i,j]$第$k$小的数。

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

$1\le n,m\le 100,000$

$1\le a_i\le 10^9$

对权值线段树进行可持久化。

从$a[1]$到$a[n]$加入每个数，询问时用第$r$棵线段树上减去第$l-1$棵线段树就能得到值域在一个区间内的数的个数。

也就是说对原数列的$[1,n]$每一个前缀$1,i$建立一棵线段树，线段树的每一个节点都存某个区间 $[L,R]$的数一共有几个。

当我们查找$[i,j]$第$k$大数时，设某节点$x$，那么$x.sum[j]-x.sum[i-1]$就是$[i,j]$中在节点$x$内的数字总数。而对每一个前缀都建一棵线段树，那么就会超出空间，观察到每个$[1,i]和[1,i-1]$只有一条路是不一样的，那么节点只要用前一棵线段树的节点就可以了。

时间和空间复杂度为$O((n+m)logn)$。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int read()
{
	int x=0,w=0;
	char ch=0;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return w? -x:x;
}
const int N=1e5+10;
struct seg_tree
{
	int l,r,s;
}t[N*20];
struct data
{
	int x,id;
	friend bool operator < (data a,data b)
	{
		return a.x<b.x;
	}
}a[N];
int rank_[N],rot[N];
int root,n,m;
void insert(int &cnt,int &tt,int l,int r)
{
	t[root++]=t[tt];
	tt=root-1;
	++t[tt].s;
	if(l==r) return;
	int mid=l+r>>1;
	if(cnt<=mid) insert(cnt,t[tt].l,l,mid);
	else insert(cnt,t[tt].r,mid+1,r);
}
int query(int i,int j,int v,int l,int r)
{
	if(l==r) return l;
	int tt=t[t[j].l].s-t[t[i].l].s;
	int mid=l+r>>1;
	if(v<=tt) return query(t[i].l,t[j].l,v,l,mid);
	else return query(t[i].r,t[j].r,v-tt,mid+1,r);
}
int main(int argc, char const *argv[])
{
	t[0].l=t[0].r=t[0].s=rot[0]=0;
	while(~scanf("%d%d",&n,&m))
	{
		for(int i=1;i<=n;++i)
			a[i].x=read(),a[i].id=i;
		sort(a+1,a+1+n);
		for(int i=1;i<=n;++i)
			rank_[a[i].id]=i;
		root=1;
		for(int i=1;i<=n;++i)
		{
			rot[i]=rot[i-1];
			insert(rank_[i],rot[i],1,n);
		}
		while(m--)
		{
			int i=read(),j=read(),k=read();
			printf("%d\n",a[query(rot[i-1],rot[j],k,1,n)].x);
		}
	}
	return 0;
}