POJ 2761(求区间第k小值)

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=100000+5;
int ch[maxn][2],val[maxn],counts[maxn],r[maxn],size[maxn],tot,root;
int num[maxn];
struct A
{
  int l,r,k,id,ans;
}a[50005];
bool cmp1(A x,A y)
{
  if(x.l == y.l) return x.r < y.r;
  return x.l  < y.l;
}
bool cmp2(A x,A y)
{
  return x.id < y.id;
}
//~~~~~~~~~~~~Treap模板~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
struct TREAP
{
    void newnode(int &rt,int v)
    {
        rt=++tot;
        val[rt]=v;
        ch[rt][0]=ch[rt][1]=0;
        counts[rt]=size[rt]=1;
        r[rt]=rand();
    }
    inline void pushup(int rt)
    {
        size[rt]=size[ch[rt][0]]+size[ch[rt][1]]+counts[rt];
    }
    void rotate(int &x,int kind)
    {
        int y=ch[x][kind^1];
        ch[x][kind^1]=ch[y][kind];
        ch[y][kind]=x;
        pushup(x);
        pushup(y);
        x=y;
    }
    void insert(int &rt,int v)
    {
        if(rt==0)
        {
            newnode(rt,v);
            return ;
        }
        if(v==val[rt]) counts[rt]++;
        else
        {
            int kind=(v>val[rt]);
            insert(ch[rt][kind],v);
            if(r[ch[rt][kind]]<r[rt])
                rotate(rt,kind^1);
        }
        pushup(rt);
    }
    int select(int rt,int k)
    {
        if(size[ch[rt][0]]>=k) return select(ch[rt][0],k);
        if(size[ch[rt][0]]+counts[rt]>=k) return val[rt];
        return select(ch[rt][1],k-size[ch[rt][0]]-counts[rt]);
    }
    void remove(int &rt,int v)
    {
        if(val[rt]==v)
        {
            if(counts[rt]>1)
                counts[rt]--;
            else if(!ch[rt][0]&&!ch[rt][1])
            {rt=0;return ;}
            else
            {
                int kind=r[ch[rt][0]]<r[ch[rt][1]];
                rotate(rt,kind);
                remove(rt,v);
            }
        }
        else remove(ch[rt][v>val[rt]],v);
        pushup(rt);
    }
    void init()
    {
        ch[0][0]=ch[0][1]=0;
        size[0]=counts[0]=val[0]=0;
        tot=root=0;
        r[0]=(1LL<<31)-1;
        newnode(root,2000000001);
    }
}treap;
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
int main()
{
    int n,m,lastl,lastr;
    while(~scanf("%d%d",&n,&m))
    {
    	treap.init();
        for (int i=1; i<=n; i++)
        scanf("%d",&num[i]);
        for(int i = 1;i <=m ;i ++)
		{
          scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].k);
          a[i].id = i;
		}
		sort(a+1,a+1+m,cmp1);
		for(int i = 1;i <= m;i ++)
		{
		  if(i == 1)
		  {
		    for(int j = a[i].l; j <= a[i].r;j ++)
			treap.insert(root, num[j]);
			a[i].ans = treap.select(root, a[i].k);
			lastl = a[i].l;
			lastr = a[i].r;
		  }
		  else
		  {

            if (a[i].l>lastr)
            {
                for (int j=lastl; j<=lastr; j++)
                treap.remove(root,num[j]);
                for (int j=a[i].l; j<=a[i].r; j++)
                treap.insert(root,num[j]);
            }
            else
            {
                for (int j=lastl; j<a[i].l; j++)
                treap.remove(root,num[j]);
                for (int j=lastr+1; j<=a[i].r; j++)
                treap.insert(root,num[j]);
            }
            a[i].ans=treap.select(root,a[i].k);
            lastl=a[i].l;
            lastr=a[i].r;
          }
       }
        sort(a+1,a+1+m,cmp2);
        for(int i = 1;i <= m;i ++)
		printf("%d\n",a[i].ans);
	 }


     return 0;
}