题意：
给定一个数组，有两种操作:
A x ：表示插入x。
Get i：表示返回第i小的数。
题解：
Treap实现名次树。
然而这道题出的比较特殊，这一个数组顺序，连续插入一段，然后输出第i大，i从1到n依次增大。可以用两个优先队列去写。
Treap实现：
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>using namespace std;struct node
{node *ch[2];int r,v,s;node(int v):v(v){s=1;ch[0]=ch[1]=NULL;r=rand();}bool operator < (const node& a)const{return r<a.r;}int cmp(int x){if(x==v)return -1;return x<v?0:1;}void maintain(){s=1;if(ch[0]!=NULL)s+=ch[0]->s;if(ch[1]!=NULL)s+=ch[1]->s;}
};void Rotate(node* &o,int d)
{node *k = o->ch[d^1];o->ch[d^1] = k->ch[d];k->ch[d]=o;o->maintain();k->maintain();o=k;
}void Insert(node* &o,int x)
{if(o==NULL)o=new node(x);else{int d = x<(o->v)?0:1;Insert(o->ch[d],x);if(o->ch[d]->r > o->r)Rotate(o,d^1);}o->maintain();
}int kth(node *o,int k)//第k小的值
{int s = (o->ch[0]==NULL)?0:o->ch[0]->s;if(k==s+1)return o->v;if(k<s+1)return kth(o->ch[0],k);return kth(o->ch[1],k-s-1);
}const int maxn=30011;
int m,n;
int a[maxn],g;int main()
{srand(100);node* root = NULL;scanf("%d%d",&m,&n);for(int i=1;i<=m;i++)scanf("%d",a+i);int j=1;for(int i=1;i<=n;i++){scanf("%d",&g);for(;j<=g;j++)Insert(root,a[j]);printf("%d\n",kth(root,i));}
}两个优先队列实现：
#include<cstdio>
#include<queue>using namespace std;priority_queue<int >pq1;
priority_queue<int,vector<int>,greater<int> >pq2;int a[33333];
int main()
{int n,m,x;scanf("%d%d",&n,&m);int k = 1;for(int i=1;i<=n;i++)scanf("%d",a+i);for(int i=1;i<=m;i++){scanf("%d",&x);while(k<=x){pq2.push(a[k]);if(pq1.size() && pq1.top() > pq2.top()){int tmp = pq1.top();pq1.pop();pq2.push(tmp);tmp = pq2.top();pq2.pop();pq1.push(tmp);}k++;}printf("%d\n",pq2.top());int tmp = pq2.top();pq2.pop();pq1.push(tmp);}
}