题意：给定M个数，每次可以插入序列一个数； 再给N个数，表示在插入第几个数时输出一个数， 第一次输出序列中最小的，第二次输出序列中第二小的……
#include <cstdio> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <cstdlib> #include <cmath> #include <utility> #include <vector> #include <queue> #include <map> #include <set> #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define INF 0x3f3f3f3f #define MAXN 30005 using namespace std; int cnt=1,rt=0; int n,m,a[MAXN],u[MAXN]; struct Tree { int key,size,pri,son[2]; void set(int x,int y,int z) { key=x; pri=y; size=z; son[0]=son[1]=0; } }T[MAXN]; void rotate(int p,int &x) { int y=T[x].son[!p]; T[x].size=T[x].size-T[y].size+T[T[y].son[p]].size; T[x].son[!p]=T[y].son[p]; T[y].size=T[y].size-T[T[y].son[p]].size+T[x].size; T[y].son[p]=x; x=y; } void ins(int key,int &x) { if(x==0) { T[x=cnt++].set(key,rand(),1); } else { T[x].size++; int p=key<T[x].key; ins(key,T[x].son[!p]); if(T[x].pri<T[T[x].son[!p]].pri) rotate(p,x); } } int find(int p,int &x) { if(p==T[T[x].son[0]].size+1) return T[x].key; if(p>T[T[x].son[0]].size+1) find(p-T[T[x].son[0]].size-1,T[x].son[1]); else find(p,T[x].son[0]); } int main() { scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int i=1;i<=m;i++) { scanf("%d",&u[i]); for(int j=u[i-1];j<u[i];j++) ins(a[j],rt); printf("%d\n",find(i,rt) ); } }