划分树静态第k大

划分树是保存了快速排序的过程的树，可以用来求静态第k小的数

如果，划分树可以看做是线段树，它的左孩子保存了mid-L+1 个小于等于 a[mid] 的数字，右孩子保存了 R-mid个大于等于a[mid]的数字

数组a是排序过后的数组，而划分树保存的是原数组的数据，

划分树的构造就是将上一层[l,r]个数的 mid-l+1个数划分到左子区间，r-(mid-l+1)个数划分到了右子区间

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

{

    if (l == r)

        return;

    int mid = (l + r) >> , isSame = mid - l + ;

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

    if (tree[rt][i] < sortA[mid])//mid-l+1个数被划入了左子树，减去比sortA[mid]小的，那么就是记录几个和其相等的被划入左子树

        isSame--;

    int lPos = l, rPos = mid + ;

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

    {

        //sum[rt][i] 为前i个数字，有多少个数字被划分到了左区间

        i == l ? sum[rt][i] =  : sum[rt][i] = sum[rt][i - ];

        if (tree[rt][i] < sortA[mid])

        {

            sum[rt][i]++;

            tree[rt+][lPos++] = tree[rt][i];

        }

        else if (tree[rt][i]>sortA[mid])

        {

            tree[rt + ][rPos++] = tree[rt][i];

        }

        else

        {

            if (isSame > )

            {

                isSame--;

                sum[rt][i]++;

                tree[rt + ][lPos++] = tree[rt][i];

            }

            else

            {

                tree[rt + ][rPos++] = tree[rt][i];

            }

        }

    }

    build(l, mid, rt + );

    build(mid + , r, rt + );

}

那么查询区间[l,r]第k大，就是如果 sum[rt][r] - sum[rt][l-1] 如果>=k, 说明该区间有sum[rt][r] - sum[rt][l-1] 个数被划分到了左子区间，

所以应该去左区间找第k小的数，否则，去右子区间找第k -（ sum[rt][r] - sum[rt][l-1] ）大的数

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

{

    int mid = (l + r) >> ;

    if (l == r)

        return tree[rt][l];

    int s1, s2;

    if (l == L)

    {

        s1 = ;

        s2 = sum[rt][R];

    }

    else

    {

        s1 = sum[rt][L - ];

        s2 = sum[rt][R] - s1;

    }

    //要记住查询的区间，同样也变化了

    if (k<=s2)

        return query(l, mid, rt + , l + s1, l + s1 + s2 - , k);

    else

        return query(mid + , r, rt + , mid  + L  - l +  - s1, mid - l +  - s1 + R  - s2 ,k-s2);

}

poj2104

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <algorithm>

#include <iostream>

#include <queue>

#include <stack>

#include <vector>

#include <map>

#include <set>

#include <string>

#include <math.h>

using namespace std;

#pragma warning(disable:4996)

#pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

const int INF = <<;

/*

*/

const int N =  + ;

int a[N], sortA[N], tree[][N],sum[][N];

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

{

    if (l == r)

        return;

    int mid = (l + r) >> , isSame = mid - l + ;

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

    if (tree[rt][i] < sortA[mid])//mid-l+1个数被划入了左子树，减去比sortA[mid]小的，那么就是记录几个和其相等的被划入左子树

        isSame--;

    int lPos = l, rPos = mid + ;

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

    {

        //sum[rt][i] 为前i个数字，有多少个数字被划分到了左区间

        i == l ? sum[rt][i] =  : sum[rt][i] = sum[rt][i - ];

        if (tree[rt][i] < sortA[mid])

        {

            sum[rt][i]++;

            tree[rt+][lPos++] = tree[rt][i];

        }

        else if (tree[rt][i]>sortA[mid])

        {

            tree[rt + ][rPos++] = tree[rt][i];

        }

        else

        {

            if (isSame > )

            {

                isSame--;

                sum[rt][i]++;

                tree[rt + ][lPos++] = tree[rt][i];

            }

            else

            {

                tree[rt + ][rPos++] = tree[rt][i];

            }

        }

    }

    build(l, mid, rt + );

    build(mid + , r, rt + );

}

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

{

    int mid = (l + r) >> ;

    if (l == r)

        return tree[rt][l];

    int s1, s2;

    if (l == L)

    {

        s1 = ;

        s2 = sum[rt][R];

    }

    else

    {

        s1 = sum[rt][L - ];

        s2 = sum[rt][R] - s1;

    }

    //要记住查询的区间，同样也变化了

    if (k<=s2)

        return query(l, mid, rt + , l + s1, l + s1 + s2 - , k);

    else

        return query(mid + , r, rt + , mid  + L  - l +  - s1, mid - l +  - s1 + R  - s2 ,k-s2);

}

int main()

{

    int n, m, k, L, R;

    int t;

    while (scanf("%d%d", &n, &m)!=EOF)

    {

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

        {

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

            tree[][i] = sortA[i] = a[i];

        }

        sort(sortA, sortA + n + );

        build(, n, );

        while (m--)

        {

            scanf("%d%d%d", &L, &R, &k);

            printf("%d\n", query(, n, , L, R, k));

        }

    }

    return ;

}

巴特西

划分树静态第k大

最新文章

热门文章

巴特西

划分树 静态第k大

最新文章

热门文章

划分树静态第k大