POJ 2104 kth-number

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

第一次寫.....
O(N(lgN)^2 + M(lgN)^3)

過惹，沒被Tㄟ，好開心~

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<cmath>
//#define min(x,y) (((x)>(y)) ? (y):(x))
//#define max(x,y) (((x)>(y)) ? (x):(y))
#define N 100005
#define INF (1000*1000*1000 + 1)
using namespace std;
vector<int> tree[4*N];
int nodecnt[4*N];
int base;
int n;
int an[N];
void setup(){
base = (1<<(int)(ceil(log2(n+2)))) - 1;
for(int lx = 0;lx < n;lx++){
tree[base + 1 + lx + 1].push_back(an[lx]);
nodecnt[base + 1 + lx + 1] = 1;
}
tree[base + 1].push_back(INF);
nodecnt[base + 1] = 0;
for(int lx = n;lx <= base;lx++){
tree[base + 1 + lx + 1].push_back(INF);
nodecnt[base + 1 + lx + 1] = 0;
}
for(int lx = base;lx;lx--){
for(int ll = 0;ll < tree[2*lx].size();ll++)
tree[lx].push_back(tree[2*lx][ll]);
for(int ll = 0;ll < tree[2*lx+1].size();ll++)
tree[lx].push_back(tree[2*lx+1][ll]);
nodecnt[lx] = nodecnt[2*lx] + nodecnt[2*lx+1];
sort(tree[lx].begin(), tree[lx].end());
/*printf("node %d:\n", lx);
for(int ll = 0;ll < tree[lx].size();ll++)
if(tree[lx][ll] >= INF)
printf("inf ");
else
printf("%03d ", tree[lx][ll]);
printf("\n");*/
}
return;
}
int query(int a, int b, int k){
a++, b++;
int seg[100], segcnt = 0;
for(a+=base-1,b+=base+1; a^b^1;a>>=1, b>>=1){
if(~a&1){
seg[segcnt] = a^1;
segcnt++;
//printf("get seg: %d\n", a^1);
}
if(b&1){
seg[segcnt] = b^1;
segcnt++;
//printf("get seg: %d\n", b^1);
}
}
int max_ele = -INF, min_ele = INF;
for(int lx = 0;lx < segcnt;lx++){
max_ele = max(max_ele, tree[seg[lx]][0]);
max_ele = max(max_ele, tree[seg[lx]][tree[seg[lx]].size()-1]);
min_ele = min(min_ele, tree[seg[lx]][0]);
min_ele = min(min_ele, tree[seg[lx]][tree[seg[lx]].size()-1]);
}
while(min_ele < max_ele){
//printf("bsh %d -> %d\n", min_ele, max_ele);
int test = (min_ele + max_ele)/2;
int check = 1;
bool found = false;
for(int lx = 0;lx < segcnt;lx++){
int getindex = lower_bound(tree[seg[lx]].begin(), tree[seg[lx]].end(), test)-tree[seg[lx]].begin();
check += getindex;
found = found or  (tree[seg[lx]][getindex] == test);
}
if(check == k){
if(found)
return test;
else{
min_ele = test+1;
//printf("giz\n");
}
}else if(check > k) max_ele = test - 1;
else if(check < k) min_ele = test + 1;
}
return min_ele;
}
int main()
{
int m;scanf("%d %d", &n, &m);
for(int lx = 0;lx < n;lx++)
scanf("%d", an+lx);
setup();
while(m--){
int a, b, k;scanf("%d %d %d", &a, &b, &k);
printf("%d\n", query(a, b, k));
}
return 0;
}