[POJ2104] 区间第k大数 [区间第k大数，可持久化线段树模板题]

可持久化线段树模板题。

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <ctime>

#include <vector>

using namespace std;

int    n,q,tot,a[];

int    root[],Left[],Right[];

int    val[];

void    Insert(const int l,const int r,const int root_l,int& root_r,const int d)

{

    val[root_r=++tot]=val[root_l]+;

    if(l==r)return ;

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

    if(d<=mid)

    {

        Right[root_r]=Right[root_l];

        Insert(l,mid,Left[root_l],Left[root_r],d);

    }

    else

    {

        Left[root_r]=Left[root_l];

        Insert(mid+,r,Right[root_l],Right[root_r],d);

    }

    return ;

}

int    Query(const int l,const int r,const int root_l,const int root_r,const int d)

{

    if(l==r)return l;

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

    temp=val[Left[root_r]]-val[Left[root_l]];

    if(temp>=d)return Query(l,mid,Left[root_l],Left[root_r],d);

    return Query(mid+,r,Right[root_l],Right[root_r],d-temp);

}

int main()

{

    freopen("in","r",stdin);

    int    i;

    vector<int>    vec;

    scanf("%d%d",&n,&q);

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

    {

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

        vec.push_back(a[i]);

    }

    sort(vec.begin(),vec.end());

    vec.erase(unique(vec.begin(),vec.end()),vec.end());

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

    {

        a[i]=lower_bound(vec.begin(),vec.end(),a[i])-vec.begin()+;

        Insert(,vec.size(),root[i-],root[i],a[i]);

    }

    for(i=;i<=q;++i)

    {

        int    l,r,k;

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

        printf("%d\n",vec[Query(,vec.size(),root[l-],root[r],k)-]);

    }

    return ;

}