insert函数

建立主席树,并且插入当前数a[ i ] (在a[ i ]的离散化编号上的节点cnt++)
刚开始建立一个空的线段树,然后不断往里面更新根节点插入数据,root[i]就是每个版本线段树
的根节点,最后求区间[l,r]之间的第k小个数只需要把找到root[l-1]版本和root[r]版本,因为每
个版本的形式一致(所以可以把root[r]版本的左子树t r[ t r [ r ] ].c n t-t r [ t r [ l-1 ] ] .c n t来求出只包含
[l,r]区间的数的线段树的做子树的已插入的数的个数,具体看query就可明白了,这里有一个二分
的思想

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#define read(x)   scanf("%d",&x)
#define write(x)  printf("%d\n",x)
using namespace std;

const int N = 100010, M = 10010;

int n, m;
int a[N];
vector<int> nums;

struct Node
{
    int l, r;
    int cnt;
}tr[N * 4 + N * 17];

int root[N], idx;

int find(int y)
{
    return lower_bound(nums.begin(),nums.end(),y)-nums.begin();
}

int build(int l,int r)
{
    int q=++idx;//写顺手了写了tr[q]={l,r},但其实不是这样
    if(l==r)    return q;
    int mid=l+r>>1;
    tr[q].l=build(l,mid),tr[q].r=build(mid+1,r);
    return q;
}
int insert(int p,int l,int r,int x)
{
    int q=++idx;
    tr[q]=tr[p];
    if(l==r) 
    {
        tr[q].cnt++;
        return q;
    }
    int mid=l+r>>1;
    if(x<=mid)  tr[q].l=insert(tr[p].l,l,mid,x);
    else tr[q].r=insert(tr[p].r,mid+1,r,x);
    tr[q].cnt=tr[tr[q].l].cnt+tr[tr[q].r].cnt;
    return q;
}
int query(int q,int p,int l,int r,int k)
{
    if(l==r)    return r;
    int cnt=tr[tr[q].l].cnt-tr[tr[p].l].cnt;
    int mid=l+r>>1;
    if(k<=cnt)  return query(tr[q].l,tr[p].l,l,mid,k);
    return query(tr[q].r,tr[p].r,mid+1,r,k-cnt);
}
int main()
{
    read(n),read(m);
    for(int i=1;i<=n;i++)
    {
        read(a[i]);
        nums.push_back(a[i]);
    }
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());//离散化
    root[0]=build(0,nums.size()-1);
    for(int i=1;i<=n;i++)
    {
        root[i]=insert(root[i-1],0,nums.size()-1,find(a[i]));
    }
    while(m--)
    {
        int l,r,k;
        read(l),read(r),read(k);
        write(nums[query(root[r],root[l-1],0,nums.size()-1,k)]);//写顺手了写了l,r 然而
        //应该是在0~nums.size()-1中找到答案
    }
    return 0;
}