poj2104(划分树模板)

poj2104

题意

给出一个序列，每次查询一个区间，要求告诉这个区间排序后的第k个数。

分析

划分树模板，O(mlogn)。

1. 建树。根据排序之后的数组，对于一个区间，找到中点的数，将整个区间分为左右子树（在子区间内数与数的相对位置保持不变），递归向下分割。
2. 查询。toleft[p][i] 表示第 p 层前 i 个数中有多少个整数分入下一层。查询最重要的是确定新的查询区间，若递归查询左区间，则新的子区间的左边一定是上一层区间 [L, l - 1] 里的 toleft[dep][l-1] - toleft[dep][L-1] 个整数，那么 newl = L + toleft[dep][l-1] - toleft[dep][L-1]，[l, r] 区间内有cnt = toleft[dep][r] - toleft[dep][l - 1] 个数，所以 newr = newl + cnt - 1；查询右区间则要先确定 newr 的值，[r+1, R] 中有 c = toleft[dep][R] - toleft[dep][r] 个整数位于左子区间的右方，所以查询区间 r 要向右移 c 个数，newr = r + c，newl = newr - (r - l - cnt)。

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

typedef long long ll;

const int INF = 1e9;

const int MAXN = 1e5 + 5;

const int LOG_N = 30;

// tree[dep][i] 第dep层第i个位置的数值

int tree[LOG_N][MAXN];

int sorted[MAXN];

// toleft[p][i] 第p层前i个数中有多少个整数分入下一层

int toleft[LOG_N][MAXN];

void build(int l, int r, int dep)

{

    if(l == r) return;

    int mid = (l + r) / 2;

    int same = mid - l + 1; // 和中点数相同的数的个数

    for(int i = l; i <= r; i++)

        if(tree[dep][i] < sorted[mid]) same--;

    int lpos = l, rpos = mid + 1;

    for(int i = l; i <= r; i++)

    {

        if(tree[dep][i] < sorted[mid])

            tree[dep + 1][lpos++] = tree[dep][i];

        else if(tree[dep][i] == sorted[mid] && same)

        {

            tree[dep + 1][lpos++] = tree[dep][i];

            same--;

        }

        else tree[dep + 1][rpos++] = tree[dep][i];

        toleft[dep][i] = toleft[dep][l - 1] + lpos - l;

    }

    build(l, mid, dep + 1);

    build(mid + 1, r, dep + 1);

}

// [L,R]里查询子区间[l,r]第k小的数

int query(int L, int R, int l, int r, int dep, int k)

{

    if(l == r) return tree[dep][l];

    int mid = (L + R) / 2;

    // 有多少个查询区间内的节点会进入下一层的左子树

    int cnt = toleft[dep][r] - toleft[dep][l - 1];

    if(cnt >= k)

    {

        int newl = L + toleft[dep][l - 1] - toleft[dep][L - 1];

        int newr = newl + cnt - 1;

        return query(L, mid, newl, newr, dep + 1, k);

    }

    else

    {

        int newr = r + toleft[dep][R] - toleft[dep][r];

        int newl = newr - (r - l - cnt);

        return query(mid + 1, R, newl, newr, dep + 1, k - cnt);

    }

}

int main()

{

    int n, m;

    while(~scanf("%d%d", &n, &m))

    {

        for(int i = 1; i <= n; i++)

        {

            scanf("%d", &sorted[i]);

            tree[0][i] = sorted[i];

        }

        sort(sorted + 1, sorted + n + 1);

        build(1, n, 0);

        while(m--)

        {

            int l, r, k;

            scanf("%d%d%d", &l, &r, &k);

            printf("%d\n", query(1, n, l, r, 0, k));

        }

    }

    return 0;

}