treap套用模板即可：

?

#include 
  
   
#include 
   
     #include 
    
      using namespace std; #define maxn 30000+5 int m,n; int a[maxn],b[maxn]; int val[maxn],ch[maxn][2],r[maxn],size[maxn],root,cnt,counts[maxn]; 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 newnode(int &rt, int v) { rt = ++ cnt; val[rt] = v; ch[rt][0] = ch[rt][1] = 0; size[rt] = counts[rt] = 1; r[rt] = rand(); } void insert(int &rt, int v) { if(rt == 0) { newnode(rt, v); return; } if(val[rt] == v) counts[rt] ++; else { int kind = (val[rt] < v); 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]); } int main() { root = 0; cnt = 0; while(scanf(%d%d,&n,&m) != EOF) { for(int i = 1;i <= n;i ++) scanf(%d, &a[i]); for(int j = 1;j <= m;j ++) scanf(%d, &b[j]); int k = 1; for(int i = 1;i <= n;i ++) { insert(root, a[i]); if(k > n) break; while(b[k] == i) { printf(%d ,select(root, k)); k ++; } } } return 0; } 
    
   
  

?

也可以使用优先队列来做，维护两个优先队列~

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; #define maxn 30000 + 5 int main() { int n, m; priority_queue
      
       , greater
       
         > q1; priority_queue
        
         , less
         
           > q2; int a[maxn],b[maxn]; while(scanf(%d%d,&n, &m) != EOF) { while(!q1.empty()) q1.pop(); while(!q2.empty()) q2.pop(); for(int i = 1;i <= n;i ++) { scanf(%d, &a[i]); } for(int j = 1;j <= m;j ++) { scanf(%d, &b[j]); } int k = 1; for(int i = 1;i <= n;i ++) { if(!q1.empty()) { if(a[i] < q1.top()) q2.push(a[i]); else { q2.push(q1.top()); q1.pop(); q1.push(a[i]); } } else q2.push(a[i]); while(b[k] == i) { if(q2.size() == k) { printf(%d ,q2.top()); } else if(q2.size() > k) { while(q2.size() != k) { q1.push(q2.top()); q2.pop(); } printf(%d ,q2.top()); } else if(q2.size() < k) { while(q2.size() != k) { q2.push(q1.top()); q1.pop(); } printf(%d ,q2.top()); } k++; } } } return 0; } 
         
        
       
      
     
    
   
  

?

?