给出一数组a，然后要求查询a[i..j]的第k大的数

划分树

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 100005;

struct Node

{

    int l,r;

    int mid()

    {

        return (l+r)>>1;

    }

} tree[N<<2];

int sorted[N];

int val[20][N],toLeft[20][N];

void build(int l,int r,int rt,int deep)// build(1,n,1,0);

{

tree[rt].l = l;//存的都是位置

    tree[rt].r  = r;

    if(l == r) return;

    int m = tree[rt].mid();

    int midval = sorted[m];

    int leftsame = m - l + 1;//表示在左子树上有多少和midval相等的数

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

    {

        if(val[deep][i] < midval)

            --leftsame;

    }

    int lpos = l,rpos = m + 1;

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

    {

        if(i == l) toLeft[deep][i] = 0;//toleft[d][i]存的是d层在i之前(包括i)小于 sa[mid] 的数的数目

//另外toLeft[][i]指的是从tree[rt].l开始到tree[rt].r范围内的，而不是以为1为开始

        else toLeft[deep][i] = toLeft[deep][i-1];//这里相当于对toLeft[][]初始化

        if(val[deep][i] < midval)

        {

            ++toLeft[deep][i];

            val[deep+1][lpos++] = val[deep][i];

        }

        else if(val[deep][i] > midval)

        {

            val[deep+1][rpos++] = val[deep][i];

        }

        else//判断和midval相等的数是放在左部还是右部

        {

            if(leftsame > 0)

            {

                --leftsame;

                ++toLeft[deep][i];

                val[deep+1][lpos++] = val[deep][i];

            }

            else//leftsame记录的左边与中间数值相等的个数。当左边的用完之后，其余的都是原先就在右边的

            {

                val[deep+1][rpos++] = val[deep][i];

            }

        }

    }

    build(l,m,rt<<1,deep+1);

    build(m+1,r,rt<<1|1,deep+1);

}

int query(int l,int r,int k,int rt,int deep)//query(a,b,c,1,0)

{

    if(l == r) return val[deep][l];

    //下面就是要确认新的查找区间

    int s;//表示[l,r]里在左边的数的个数//s表示区间[l,r]有多少个小于sa[mid]的数被分到左边  

    int ss;//表示[tree[rt].l...l-1]里在左边的数的个数

    if(l == tree[rt].l)

    {

        s = toLeft[deep][r];

        ss = 0;

    }

    else

    {

        ss = toLeft[deep][l-1];//ss并不是等于l-1，因为这l-1个数里面有的移到左边，有的移动到右边，这就是toLeft数组的作用

        s = toLeft[deep][r] - ss;

    }

    if(s >= k)//区间【l,r】分到左边的数大于K，那么第K大的数也在左子树

    {

        /*进入左子树  */

        int newl = tree[rt].l + ss;//在子树新的起点=子树起始点+前面更小的一段

        int newr = newl + s - 1;//在子树新的终点

        return query(newl,newr,k,rt<<1,deep+1);

    }

    else

    {

        int m = tree[rt].mid();

        int b = r - l + 1 - s;//[L,R]这么一段本身的长度减去进入左子树的长度=进入右子树的长度（第K个在里面）

        int bb = (l - 1) - tree[rt].l + 1 - ss;

//(l - 1) - tree[rt].l + 1表示[tree[rt].l,l-1]的长度，再减去它在左边部分的长度，得到[tree[rt].l,l-1]在右边的数的个数

        int newl = m + 1 + bb;//m+1是中点的起点

        int newr = m + b + bb;//m + r - l + 1 - toLeft[deep][r] + ss - l - tree[rt].l - ss = m+r-

        return query(newl,newr,k-s,rt<<1|1,deep+1);

    }

}

static inline int Rint()//这段是整型数的输入外挂，可以忽略不用看

{

    struct X

    {

        int dig[256];

        X()

        {

            for(int i = ‘0‘; i <= ‘9‘; ++i) dig[i] = 1;

            dig[‘-‘] = 1;

        }

    };

    static  X fuck;

    int s = 1, v = 0, c;

    for (; !fuck.dig[c = getchar()];);

    if (c == ‘-‘) s = 0;

    else if (fuck.dig[c]) v = c ^ 48;

    for (; fuck.dig[c = getchar()]; v = v * 10 + (c ^ 48));

    return s ? v : -v;

}

int main()

{

    int n,m;

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

    {

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

        {

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

            sorted[i] = val[0][i];

        }

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

        build(1,n,1,0);

        while(m--)

        {

            int a,b,c;

            scanf("%d %d %d",&a,&b,&c);

            printf("%d\n",query(a,b,c,1,0));

        }

    }

    return 0;

}

TreeSegment2104_DivideTree