题意：

给你个序列和一串询问 询问前a[i]个数字第i小的是几

思路：

动态的第k值问题 由于区间只增不减所以是水题

利用平衡树解决这类问题

treap是方便编写的类似平衡树的产品

treap方便实现BST的功能 splay更适合于去维护区间

代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        using namespace std; #define N 30010 #define inf ((1U<<31)-1) #define L(x) (ch[x][0]) #define R(x) (ch[x][1]) int ch[N][2],val[N],priority[N],num[N],size[N]; int tot,root; int newnode(int &u,int w) { u=++tot; L(u)=R(u)=0; priority[u]=rand(); num[u]=size[u]=1; val[u]=w; return u; } inline void up(int u) { size[u]=size[L(u)]+size[R(u)]+num[u]; } void rotate(int &u,int kind) { int y=ch[u][kind^1]; ch[u][kind^1]=ch[y][kind]; ch[y][kind]=u; up(u); up(y); u=y; } int insert(int &u,int w) { if(!u) return newnode(u,w); int res,kind; if(w==val[u]) { num[u]++; res=u; } else { kind=(w>val[u]); res=insert(ch[u][kind],w); if(priority[ch[u][kind]]
       
        =k) return select(L(u),k); if(size[L(u)]+num[u]>=k) return val[u]; return select(R(u),k-size[L(u)]-num[u]); } void remove(int &u,int w) { if(val[u]==w) { if(num[u]>1) num[u]--; else if(!L(u)&&!R(u)) { u=0; return ; } else { int kind=(priority[L(u)]
        
         val[u]],w); up(u); } void init() { R(0)=L(0)=size[0]=num[0]=val[0]=0; priority[0]=inf; tot=root=0; newnode(root,inf); } int n,m; int a[N],b[N]; int main() { int i,j; while(~scanf("%d%d",&n,&m)) { srand(n*5-m+19930909); init(); for(i=1;i<=n;i++) scanf("%d",&a[i]); for(j=1;j<=m;j++) scanf("%d",&b[j]); for(j=1,i=1;j<=m;j++) { while(i<=b[j]) { insert(root,a[i]); i++; } printf("%d\n",select(root,j)); } } return 0; }