听老师讲课，越来越感觉自己学的太少了啊，，，还有太多东西没学，最近效率太低了。
划分树和归并树相似，不过归并树是从有序到无序（）
而划分树则是从无序到有序

（红色部分代表进入左子树的数值）
划分树中每个节点记录两个信息， 
struct node
{
    int num[MAXN],cnt[MAXN];
    //num,该层储存的数组
    //cnt[i]表示此层i节点向左有多少数值进入左子树
} tree[20];//tree[deep]代表深度为deep的那一层

建树

确定一层中某个数值进入左子树还是右子树，依靠一个原数组排序后的sort【mid】的值确定，
同时为了

有空重新画吧。。不过虽然丑意思还是在的。。）
为了使划分树的每一节点的元素等于区间长度
我们对于相等的数，就不能全部放到左子树
只能放一部分给左子树
void build(int t,int L,int R)
{
    if (L==R)
        return;
    int mid=(L+R)>>1,key=sorted[mid],scnt=mid-L+1,i;
    for(i=L; i<=R; ++i)
        if(tree[t].num[i]<key)
            --scnt;//计算有多少等于sort[mid]的元素要进入左子树
    int l=L-1,r=mid,cnt=0;
    for (i=L; i<=R; ++i)
    {
        int num=tree[t].num[i];
        if (num < key || (num == key && scnt))
        {
            //把小于等于key的数放入左树，否则放入右树
            if (num == key)
                --scnt;
            ++cnt;
            tree[t+1].num[++l]=num;
        }
        else
            tree[t+1].num[++r]=num;
        tree[t].cnt[i]=cnt;
        //记录当前放入左树的数的个数
    }
    build(t+1,L,mid);
    build(t+1,mid+1,R);
}


查询



摘自：https://blog.csdn.net/Akatsuki__Itachi/article/details/80030929
对我又懒了）
附求区间第k大板子 
//#include <bits/stdc++.h>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<stack>
#include<ctime>
#include<cstdio>
#include<vector>
#include<string>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
#define pi  acos(-1.0)
#define INF  0x3f3f3f3f
#define mod   1000000009
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
struct node
{
    int num[MAXN],cnt[MAXN];
    //num,该层储存的数组
    //cnt[i]表示此层i节点向左有多少数值进入左子树
} tree[20];//tree[deep]代表深度为deep的那一层
int sorted[MAXN],ans;
void build(int t,int L,int R)
{
    if (L==R)
        return;
    int mid=(L+R)>>1,key=sorted[mid],scnt=mid-L+1,i;
    for(i=L; i<=R; ++i)
        if(tree[t].num[i]<key)
            --scnt;//计算有多少等于sort[mid]的元素要进入左子树
    int l=L-1,r=mid,cnt=0;
    for (i=L; i<=R; ++i)
    {
        int num=tree[t].num[i];
        if (num < key || (num == key && scnt))
        {
            //把小于等于key的数放入左树，否则放入右树
            if (num == key)
                --scnt;
            ++cnt;
            tree[t+1].num[++l]=num;
        }
        else
            tree[t+1].num[++r]=num;
        tree[t].cnt[i]=cnt;
        //记录当前放入左树的数的个数
    }
    build(t+1,L,mid);
    build(t+1,mid+1,R);
}
void query(int t,int L,int R,int l,int r,int k)
{
    if (L==R)
    {
        ans=tree[t].num[L];
        return;
    }
    int mid=(L+R)>>1,left=0,sum_l=tree[t].cnt[r],new_l,new_r;
    if (L != l)
    {
        left=tree[t].cnt[l-1];
        sum_l-=left;
    }
    if (sum_l >= k)
    {
        new_l=L+left;
        new_r=new_l+sum_l-1;
        query(t+1,L,mid,new_l,new_r,k);
    }
    else
    {
        new_l=mid+1+l-L-left;
        new_r=new_l+r-l-sum_l;
        query(t+1,mid+1,R,new_l,new_r,k-sum_l);
    }
}
int main()
{
    int n,m,i,l,r,k;
    while (~scanf("%d%d",&n,&m))
    {
        for (i=1; i<=n; ++i)
        {
            scanf("%d",sorted+i);
            tree[0].num[i]=sorted[i];
        }
        sort(sorted+1,sorted+n+1);
        build(0,1,n);
        while (m--)
        {
            scanf("%d%d%d",&l,&r,&k);
            query(0,1,n,l,r,k);
            printf("%d\n",ans);
        }
    }

}