#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
int n,m;
int num[100010];
struct node{
       int x,r,size[2];
       node *ch[2];
}*root;
int temp;
node *New(int x){
     node *p=new node;
     p->x=x,p->r=rand()*rand(),p->ch[0]=p->ch[1]=NULL,p->size[0]=p->size[1]=0;
     return p;
}
void Rotate(node* &x,int t){
     node *p=x->ch[t];
     x->ch[t]=p->ch[!t],x->size[t]=p->size[!t];
     p->ch[!t]=x,p->size[!t]=x->size[t]+x->size[!t]+1;
     x=p;
}
void Insert(node* &now,node* newnode){
     if (now==NULL) {
                    now=newnode;
                    return;
                    }
     int t=newnode->x>now->x;
     now->size[t]++;
     Insert(now->ch[t],newnode);
     if (now->ch[t]->r>now->r) Rotate(now,t);
}
void search(node* &now,int x){
     if (x<=now->size[0]) search(now->ch[0],x);
     else{
          if (x==now->size[0]+1) {
                                 temp=now->x;
                                 return;
                                 }
          else search(now->ch[1],x-now->size[0]-1);
          }
}
int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    srand(time(NULL));
    scanf("%d %d\n",&n,&m);
    for (int i=1;i<=n;i++){
        scanf("%d",&num[i]);
    }
    int a,b,c;
    for (int i=1;i<=m;i++){
        scanf("\n%d %d %d",&a,&b,&c);
        root=NULL;
        for (int j=a;j<=b;j++){
            Insert(root,New(num[j]));
        }
        search(root,c);
        printf("%d\n",temp);
    }
    return 0;
}

• Re:我的treap为什么Runtime Error (1792) slashdot 2011-05-19 13:55:51
• 用G++提交貌似会RE (57) qq836793 2014-04-10 15:07:14