传送门
照理来说很久很久以前就做过这个题（并且做过很多很多遍），但是从来没有写过…
于是趁这个机会学了Treap（好吧感觉就是对着蓝书抄了一遍不知道记住了多少），发现Treap比我想象中简单好多。然后正解是对顶堆吧。用优先队列不开O2和Treap根本没差多少啊0 0

Treap版
那个root[2]是最开始开了2e5的数组发现其实只用了root[1]

#include<bits/stdc++.h> using namespace std; const int N=200002; int n,m,a[N],u[N]; struct node{ int r,v,s; node *ch[2]; int cmp(int x){ return x>v; } node(int v):v(v) { ch[0]=ch[1]=NULL;r=rand();s=1; } void maintain(){ s=1; if (ch[0]!=NULL) s+=ch[0]->s; if (ch[1]!=NULL) s+=ch[1]->s; } }; node* root[2]; void read(int &x){ char ch=getchar();x=0;int w=1; for(;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') w=-1; for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0'; x*=w; } void rorate(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 add(int x,node* &o){ if (o==NULL) o=new node(x); else{ int d=o->cmp(x); add(x,o->ch[d]); if (o->ch[d]->r>o->r) rorate(o,d^1); } o->maintain(); } int get(node* &o,int k){ // if (o==NULL) return 0; int s=(o->ch[0]==NULL?0:o->ch[0]->s); if (k==s+1) return o->v; else if (k<=s) return get(o->ch[0],k); else return get(o->ch[1],k-s-1); } int main(){ freopen("1.in","r",stdin); freopen("1.out","w",stdout); read(n);read(m); for(int i=1;i<=n;i++) read(a[i]); for(int i=1;i<=m;i++) read(u[i]); int j=1; for(int i=1;i<=n;i++){ add(a[i],root[1]); for(;u[j]==i;cout<<get(root[1],j)<<endl,j++); } return 0; }

然后是堆

#include<bits/stdc++.h> using namespace std; const int N=200002; int n,m,a[N],u[N]; priority_queue<int> h1; priority_queue<int,vector<int>,greater<int> > h2; void read(int &x){ char ch=getchar();x=0;int w=1; for(;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') w=-1; for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0'; x*=w; } int main(){ freopen("1.in","r",stdin); freopen("1.out","w",stdout); read(n);read(m); for(int i=1;i<=n;i++) read(a[i]); for(int i=1;i<=m;i++) read(u[i]); int j=1;h1.push(-2e9-1); for(int i=1;i<=n;i++){ if (a[i]<h1.top()) h2.push(h1.top()),h1.pop(),h1.push(a[i]); else h2.push(a[i]); for(;u[j]==i;j++){ int x=h2.top(); cout<<x<<endl; h1.push(x);h2.pop(); } } return 0; }