POJ_2761

    本来想搜一下SBT的题练一下昨天刚学的SBT的，但这种查询静态区间内的kth number的题目还是用划分树更好写一些，所以就用划分树写了，就当是复习一下前几天学的划分树了。

#include
     
       #include
      
        #include
       
         #define MAXD 100010 int N, M, rank[20][MAXD], sa[MAXD], a[MAXD], h[20][MAXD]; int cmp(const void *_p, const void *_q) {
   int *p = (int *)_p, *q = (int *)_q; if(a[*p] == a[*q]) return *p - *q; return a[*p] < a[*q] ? -1 : 1; } void init() {
   int i, j, k; for(i = 1; i <= N; i ++)     {
           scanf("%d", &a[i]);         sa[i] = i;     }     qsort(sa + 1, N, sizeof(sa[0]), cmp); } void build(int x, int y, int d) {
   if(x == y) return ; int i, p = 0, mid = (x + y) / 2; for(i = x; i <= y; i ++)     {
   if(rank[d][i] <= mid)         {
               rank[d + 1][x + p] = rank[d][i];             ++ p;         } else             rank[d + 1][mid + i - x + 1 - p] = rank[d][i];         h[d][i] = p;     }     build(x, mid, d + 1);     build(mid + 1, y, d + 1); } int search(int x, int y, int tx, int ty, int d, int k) {
   if(x == y) return a[sa[rank[d][x]]]; int n, m, mid = (x + y) / 2;     n = tx == x ? 0 : h[d][tx - 1];     m = h[d][ty]; if(k <= m - n) return search(x, mid, x + n, x + m - 1, d + 1, k); else return search(mid + 1, y, mid + 1 + tx - x - n, mid + 1 + ty - x - m, d + 1, k - m + n); } void solve() {
   int i, j, k, x, y; for(i = 1; i <= N; i ++)         rank[0][sa[i]] = i;     build(1, N, 0); for(i = 0; i < M; i ++)     {
           scanf("%d%d%d", &x, &y, &k);         printf("%d\n", search(1, N, x, y, 0, k));     } } int main() {
   while(scanf("%d%d", &N, &M) == 2)     {
           init();         solve();     } return 0; }