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.InputThe 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 9 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).OutputFor 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.
很裸的主席树模板题。不知道可不可以用O（n1.5log2n）的莫队加平衡树来做。
如果用下面这段代码去过poj的话会T掉，如果不是用new动态分配内存而是直接分配一个数组，在数组中储存所有节点可能就可以过了。
Code
/**
* OpenJudge
* Bailian#2104
* Accepted
* Time:2247ms
* Memory:65536k
*/
#include<iostream>
#include<fstream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
using namespace std;
typedef bool boolean;
#define smin(a, b) (a) = min((a), (b))
#define smax(a, b) (a) = max((a), (b))
template<typename T>
inline void readInteger(T& u){
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != '-' && x != -);
if(x == -){
ungetc(x, stdin);
return;
}
if(x == '-'){
x = getchar();
aFlag = -;
}
for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');
ungetc(x, stdin);
u *= aFlag;
} typedef class SegTreeNode{
public:
int s; //size
SegTreeNode *left, *right;
SegTreeNode():left(NULL), right(NULL), s(){ }
void pushUp(){
this->s += this->left->s + this->right->s;
}
}SegTreeNode; typedef class SegTree{
public:
SegTreeNode* root;
SegTree():root(NULL){ }
SegTree(int size, int val){
build(root, , size, val);
}
SegTree(SegTreeNode* root):root(root){ } void build(SegTreeNode*& node, int from, int end, int val){
node = new SegTreeNode();
if(from == end){
node->s = (val == from) ? () : ();
return;
}
int mid = (from + end) >> ;
build(node->left, from, mid, val);
build(node->right, mid + , end, val);
node->pushUp();
}
}SegTree; typedef class Pair{
public:
int data;
int index;
Pair(const int data = , const int index = ):data(data), index(index){ }
boolean operator < (Pair another) const {
return data < another.data;
}
}Pair; typedef class ChairTree{ //主席树
public:
SegTree* st;
int* discrete;
map<int, int> to;
int len;
ChairTree():st(NULL), discrete(NULL){ }
ChairTree(int* lis, int len):len(len){
discrete = new int[(const int)(len + )];
memcpy(discrete, lis, sizeof(int) * (len + ));
sort(discrete + , discrete + len + );
for(int i = ; i <= len; i++)
to[discrete[i]] = i;
st = new SegTree[(const int)(len + )];
st[] = SegTree(len, );
for(int i = ; i <= len; i++){
st[i] = SegTree();
appendSegTree(st[i].root, st[i - ].root, , len, to[lis[i]]);
}
} void appendSegTree(SegTreeNode*& node, SegTreeNode*& before, int from, int end, int val){
node = new SegTreeNode();
if(from == end){
node->s = ;
return;
}
int mid = (from + end) >> ;
if(val <= mid){
node->right = before->right;
appendSegTree(node->left, before->left, from, mid, val);
}else{
node->left = before->left;
appendSegTree(node->right, before->right, mid + , end, val);
}
node->pushUp();
} int query(int l, int r, SegTreeNode*& left, SegTreeNode*& right, int k){
if(l == r){
return l;
}
int ls = left->left->s - right->left->s;
int mid = (l + r) >> ;
if(ls >= k) return query(l, mid, left->left, right->left, k);
return query(mid + , r, left->right, right->right, k - ls);
} int query(int from, int end, int k){
return discrete[query(, len, st[end].root, st[from - ].root, k)];
}
}ChairTree; int n, m;
ChairTree ct;
int *lis; inline void init(){
readInteger(n);
readInteger(m);
lis = new int[(const int)(n + )];
for(int i = ; i <= n; i++){
readInteger(lis[i]);
}
ct = ChairTree(lis, n);
} inline void solve(){
int l, r, k;
while(m--){
readInteger(l);
readInteger(r);
readInteger(k);
int res = ct.query(l, r, k);
printf("%d\n", res);
}
} int main(){
init();
solve();
return ;
}