kth number RMQ revisit

http://poj.org/problem?id=2104

O((N+M)logN)

用ㄎㄠ線段樹:3

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#define min(x,y) (((x)>(y)) ? (y):(x))
#define max(x,y) (((x)>(y)) ? (x):(y))
#define NN 100015
using namespace std;
typedef struct _node{ int left_ind; int right_ind; int count; }node;
int an[NN];int n;
node tree[NN*40]; /** 2N + NlgN **/
int sz =0;
int tline[NN];
int tline_sz;
int cownod[NN];
int _step = 0;
void test_step(){_step++; if(_step/3000 >= 1000) printf("%d\n", 1/0);}
void _assert(bool t){if(t == false)printf("%d", 1/0); return;}
inline int make(int l, int r){
test_step();
int prc_ind = sz; sz++;
tree[prc_ind].count = 0;
tree[prc_ind].left_ind = -9999999, tree[prc_ind].right_ind =-9999999;
if(l >= r) return prc_ind;
int mid = (l+r)>>1;
tree[prc_ind].left_ind = make(l, mid);
tree[prc_ind].right_ind = make(mid+1, r);
return prc_ind;
}
int jizz(int rt_ind, int jiz_ind, int l, int r){
_assert(rt_ind>=0);
test_step();
int newrt_ind = sz; sz++;
tree[newrt_ind] = tree[rt_ind];
tree[newrt_ind].count++;
if(l == r) return newrt_ind;
_assert(jiz_ind >= l and jiz_ind <= r);
int mid = (l+r)>>1;
// left = l ~ mid, right = mid+1 ~ r
if(jiz_ind <= mid){ //left
int newleft_ind = jizz(tree[rt_ind].left_ind, jiz_ind, l, mid);
tree[newrt_ind].left_ind = newleft_ind;
}else{
int newright_ind = jizz(tree[rt_ind].right_ind, jiz_ind, mid+1, r);
tree[newrt_ind].right_ind = newright_ind;
}
return newrt_ind;
}

inline int read(int lrt, int rrt, int k){
//printf("read [%d~%d]\n", tleft, tright);
int tleft = 0, tright = tline_sz+1;
while(tleft < tright){
test_step();
int tmid = (tleft+tright)>>1;
int leftcnt = tree[tree[rrt].left_ind].count - tree[tree[lrt].left_ind].count;
if(k <= leftcnt){
lrt = tree[lrt].left_ind, rrt = tree[rrt].left_ind;
tright = tmid;
}else{
lrt = tree[lrt].right_ind, rrt = tree[rrt].right_ind;
tleft = tmid+1;
k -= leftcnt;
}
}
return tleft;
}
void printtree(int rt){
if(tree[rt].left_ind == -1){
printf("%d ", tree[rt].count);
return;
}
//printf(" %d:{", tree[rt].count);
printtree(tree[rt].left_ind);
printtree(tree[rt].right_ind);
//printf("}");
}
int main()
{
int m;scanf("%d %d", &n, &m);
for(int lx = 0;lx < n;lx++) scanf("%d", an+lx), tline[lx] = an[lx];
sort(tline, tline+n);
tline_sz = n;
//printf("%d\n", tline_sz);
map<int, int> arctline;
_assert(tline_sz == n);
cownod[0] = make(0, tline_sz+1);
for(int lx = 0;lx < n;lx++){
int pos = lower_bound(tline,tline+n,an[lx]) - tline;
cownod[1+lx] = jizz(cownod[lx], pos, 0, tline_sz+1);
}
/*for(int lx = 0;lx <= n;lx++){
printtree(cownod[lx]);puts("");
}*/
while(m-->0){
int ll, rr, k;scanf("%d %d %d", &ll, &rr, &k);
printf("%d\n", tline[read(cownod[ll-1], cownod[rr], k)]);
}
return 0;
}