hdu2665

题解：

裸的主席树，记录最小值

代码：

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

using namespace std;

const int N=;

int a[N],cnt,Case,rt[N],b[N],now,n,m,x,y,k;

struct Tree

{

    int ls,rs,num;

}T[N*];

int ef(int x)

{

    int l=,r=cnt;

    while (l<r)

     {

         int mid=(l+r)/;

         if (b[mid]<x)l=mid+;

         else r=mid;

     }

    return l;

}

int build(int l,int r)

{

    now++;

    if (l==r)return now;

    int k=now,mid=(l+r)/;

    if (l<=mid)T[k].ls=build(l,mid);

    if (mid<r)T[k].rs=build(mid+,r);

    return k;

}

int insert(int x,int l,int r,int s)

{

    now++;

    if (l==r)

     {

         T[now].num=T[x].num+;

         return now;

     }

    int k=now,mid=(l+r)/;

    if (s<=mid)

     {

         T[k].ls=insert(T[x].ls,l,mid,s);

         T[k].rs=T[x].rs;

     }

    else

     {

         T[k].ls=T[x].ls;

         T[k].rs=insert(T[x].rs,mid+,r,s);

     }

    T[k].num=T[T[k].ls].num+T[T[k].rs].num;

    return k;

}

int find(int x,int y,int z,int l,int r)

{

    if (l==r)return l;

    if (T[T[x].ls].num-T[T[y].ls].num>=z)

     return find(T[x].ls,T[y].ls,z,l,(l+r)/);

    return find(T[x].rs,T[y].rs,z-

    T[T[x].ls].num+T[T[y].ls].num,(l+r)/+,r);

}

int main()

{

    scanf("%d",&Case);

    while (Case--)

     {

         memset(T,,sizeof T);

         now=;

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

         for (int i=;i<=n;i++)scanf("%d",&a[i]);

         for (int i=;i<=n;i++)b[i]=a[i];

         sort(b+,b+n+);

         cnt=;

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

          if (b[i]!=b[i-])b[++cnt]=b[i];

         for (int i=;i<=n;i++)a[i]=ef(a[i]);

        rt[]=build(,n);

        for (int i=;i<=n;i++)rt[i]=insert(rt[i-],,n,a[i]);

        while (m--)

         {

             scanf("%d%d%d",&x,&y,&k);

             printf("%d\n",b[find(rt[y],rt[x-],k,,n)]);

         }

     }

}