法一:对顶堆 40ms
用两个堆分别维护最大值和最小值,通过平衡两个堆的数量来维护第i大
void solve(){
n=read(),m=read();
rep(i,1,n) a[i]=read();
rep(i,1,m) b[i]=read();
priority_queue<int> down;
priority_queue<int,vector<int>,greater<int>> up;
int k=0;
for(int i=1,j=1;i<=m;++i){
while(j<=b[i]){
if(down.empty() || a[j] >= down.top()) up.push(a[j]);
else{
up.push(down.top());
down.pop();
down.push(a[j]);
}
j++;
}
down.push(up.top());
up.pop();
print(down.top());
}
}
法二:动态开点权值线段树 60ms
开一棵动态开点的权值线段树维护[-2e9,2e9]区间内的信息
然后每次查询在线段树上二分找到第i大数即可
#define N 50010
#define VL -2e9
#define VR 2e9
struct ValueSegment_Tree{
struct Node{LL ls,rs,sum;}tr[N<<5];
LL idx=1,root=1;
#define push_up(u) tr[u].sum=tr[tr[u].ls].sum+tr[tr[u].rs].sum;
void insert(LL &u,LL l,LL r,int d){
if(!u) u=++idx;
if(l==r) {tr[u].sum++;return ;}
LL mid=l+r>>1;
if(d<=mid) insert(tr[u].ls,l,mid,d);
else insert(tr[u].rs,mid+1,r,d);
push_up(u);
}
int query(LL u,LL l,LL r,int k){
if(l==r) return l;
LL mid=l+r>>1;
if(tr[tr[u].ls].sum>=k) return query(tr[u].ls, l, mid, k);
else return query(tr[u].rs, mid+1, r, k-tr[tr[u].ls].sum);
}
}T;
int n,m,a[N],g[N];
void solve(){
m=read(),n=read();
rep(i,1,m) a[i]=read(); rep(i,1,n) g[read()]++;
for(int i=1,rk=1;i<=m;++i){
T.insert(T.root, VL, VR, a[i]);
while(g[i]--) print(T.query(T.root,VL,VR,rk++));
}
}
啊
妙