线段树区间更新+单调性+思维——cf1326E(好题)
首先,答案具有单调性,所以我们用一个指针pos指向第k大的值
然后来考虑一个点不会被炸掉的情况(考虑到这个点时,所有比其大的点已经更新在线段树里)
必须是这个点及其后面位置的x个炸弹炸不到它
线段树维护前i个位置的点被炸完还需要的炸弹数,我们再维护一个Max,那么当Max[root]>0时,表示还有点可以留下来
考虑更新:位置i的炸弹可以炸的位置是[1,i],所以这个区间Max -1
位置i的点则会给[1,i] 的Max +1
虽然cf这种题很常见,但是感觉这题思维量好大。。
#include<bits/stdc++.h> using namespace std; #define N 300005 int ans[N],n,p[N],q[N],id[N]; int cmp(int a,int b){return p[a]>p[b];} #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int Max[N<<2],lazy[N<<2]; void pushdown(int rt){ if(lazy[rt]){ Max[rt<<1]+=lazy[rt]; Max[rt<<1|1]+=lazy[rt]; lazy[rt<<1]+=lazy[rt]; lazy[rt<<1|1]+=lazy[rt]; lazy[rt]=0; } } void update(int L,int R,int v,int l,int r,int rt){ if(L<=l && R>=r){ Max[rt]+=v;lazy[rt]+=v;return; } pushdown(rt); int m=l+r>>1; if(L<=m)update(L,R,v,lson); if(R>m)update(L,R,v,rson); Max[rt]=max(Max[rt<<1],Max[rt<<1|1]); } int query(int L,int R,int l,int r,int rt){ if(L>R)return 0; if(L<=l && R>=r)return Max[rt]; pushdown(rt); int m=l+r>>1,res=-1000000; if(L<=m)res=max(res,query(l,R,lson)); if(R>m)res=max(res,query(L,R,rson)); return res; } int main(){ cin>>n; for(int i=1;i<=n;i++)scanf("%d",&p[i]); for(int i=1;i<=n;i++)scanf("%d",&q[i]); for(int i=1;i<=n;i++)id[i]=i; sort(id+1,id+1+n,cmp); int pos=1;update(1,id[pos],1,1,n,1); for(int i=1;i<=n;i++){ while(1){ if(Max[1]>0)break; else { pos++; update(1,id[pos],1,1,n,1); } } cout<<p[id[pos]]<<" "; update(1,q[i],-1,1,n,1); } }