学步园

POJ_2761

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

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#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;
}