[POJ2104]K-th Number

1. K-th Number

Time Limit: 20000MS		Memory Limit: 65536K
Total Submissions: 34048		Accepted: 10810
Case Time Limit: 2000MS

Description

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.

Input

The first line of the input file contains n --- the size of the array, and m --- the number of questions to answer (1 <= n <= 100 000, 1 <= m <= 5 000). 
The second line contains n different integer numbers not exceeding 10⁹ by their absolute values --- the array for which the answers should be given. 
The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k).

Output

For each question output the answer to it --- the k-th number in sorted a[i...j] segment.

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

This problem has huge input,so please use c-style input(scanf,printf),or you may got time limit exceed.

Source

Northeastern Europe 2004, Northern Subregion

一句话题意：题目意思很简单，多次询问区间k小值

分析：没什么好分析的，模板题，原本想用划分树做，然后去贴吧问……结果被喷“时代的默泪”，ORZ……然后默默的去看主席树了

（主席树资料网上很多，大家百度一下）

这里说下主要思想，就是对1~n每个位置建立一颗线段树，表示从开头到此位置每个数字在各个区间出现次数（当然要先离散……），当然这样空间不行，但是可以发现所有线段树形状一样只是sum域不同，且第i颗和第i-1颗相比，只是在第i-1颗的基础上插入了第i个点（即只修改了第i-1颗线段树的一条从上到下的路径，其他都没改变)，因此只要建立一个主线段树，没变的指一条边过去就可以了。

然后询问[a,b]可以发现线段树可以减，即[a,b]的线段树相当于[1,b]线段树(对应第b颗线段树)-[1,a-1]线段树(对应第a-1颗)，然后判断下左子树大小和k的关系就行了

code:

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100010;
struct wjmzbmr
{
 int l,r,ls,rs,sum;
}f[maxn*20];
int tot,root[maxn+50],q,b[maxn+50],sortb[maxn+50];
int build(int l,int r)
{
 int k=++tot;
 f[k]={l,r,0,0,0};
 if(l==r) return tot;
 int mid=(l+r)>>1;
 f[k].ls=build(l,mid);
 f[k].rs=build(mid+1,r);
 return k;
}
int change(int o,int x,int v)
{
 int k=++tot;
 f[k]=f[o];f[k].sum+=v;
 if(f[o].l==x&&f[o].r==x) return k;
 int mid=(f[o].l+f[o].r)>>1;
 if(x<=mid) f[k].ls=change(f[o].ls,x,v);else f[k].rs=change(f[o].rs,x,v);
 return k; 
}
int ask(int a,int b,int k)
{
 if(f[b].l==f[b].r) return f[b].l;
 int mid=f[f[b].ls].sum-f[f[a].ls].sum;
 if(k<=mid) return ask(f[a].ls,f[b].ls,k);else return ask(f[a].rs,f[b].rs,k-mid);
}
int main()
{
 freopen("ce.in","r",stdin);
 freopen("ce.out","w",stdout);
 int n,m;
 while(scanf("%d%d",&n,&m)!=EOF)
 {
  for(int i=1;i<=n;++i) scanf("%d",&b[i]),sortb[i]=b[i];
  sort(sortb+1,sortb+1+n);
  q=1;tot=0;
  for(int i=2;i<=n;++i) if(sortb[q]!=sortb[i]) sortb[++q]=sortb[i];
  root[0]=build(1,q);
  for(int i=1;i<=n;++i)
  {   
   int p=lower_bound(sortb+1,sortb+n+1,b[i])-sortb;
   root[i]=change(root[i-1],p,1);
  }
  for(int i=1;i<=m;++i)
  {
   int a,b,k;
   scanf("%d%d%d",&a,&b,&k);
   printf("%d
",sortb[ask(root[a-1],root[b],k)]);
  }
 }
 return 0;
}