1326E - Bombs_牛客博客

题目链接
思路：显然答案是单调不增的。
根据这个性质，我们可以枚举答案来检查答案是否合法。
假设第 $i - 1$ 次的答案为 $x$ ，此时我们在 $q_{i}$ 位置新加入了一个炸弹，那么当前存在炸弹的位置就是 $q_{1}, q_{2} . . . . . q_{i}$ 。
如果存在一个位置 $y$ ，使得 $[y, n]$ 上 $\geq x$ 的 $p_{i}$ 的个数大于 $[y, n]$ 上炸弹的个数，那么此时的答案 $x$ 就是合法的。
那么我们维护一个 $b$ 数组, $b_{i} = [i, n]$ 上大于等于 $x$ 的数的个数 $- [i, n]$ 上炸弹的个数。
当前仅当 $b$ 的最大值>0时， $x$ 才合法。
否则，我们把 $x$ 变小，再更新 $b$ 数组进行判断即可。
细节见代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
#define fi first
#define se second
#define pb push_back
#define mid (l+r>>1)
#define ls o<<1
#define rs o<<1|1
int n,a[N],b[N],pos[N];
int t[N<<2],lz[N<<2];
void pd(int o){
  if(lz[o]){
    lz[ls]+=lz[o];
    lz[rs]+=lz[o];
    t[ls]+=lz[o];
    t[rs]+=lz[o];
    lz[o]=0;
  }
}
void up(int o,int l,int r,int x,int y,int d){
  if(l>=x&&r<=y){
    t[o]+=d;
    lz[o]+=d;
    return ;
  }
  pd(o);
  if(x<=mid)up(ls,l,mid,x,y,d);
  if(y>mid)up(rs,mid+1,r,x,y,d);
  t[o]=max(t[ls],t[rs]);
}
int ge(int o,int l,int r,int x,int y){
  if(l>=x&&r<=y){
    return t[o];
  }
  pd(o);
  int ans=-1e9;
  if(x<=mid)ans=max(ans,ge(ls,l,mid,x,y));
  if(y>mid)ans=max(ans,ge(rs,mid+1,r,x,y));
  return ans;
}
int po=1e9,ans;
int ge(){
  if(t[1]>0)return 1;//合法
  ans--;
  up(1,1,n,1,pos[ans],1);//不合法我们更新
  return 0;
}
int main(){
  ios::sync_with_stdio(false);
  cin>>n;ans=n;
  for(int i=1;i<=n;i++)cin>>a[i],pos[a[i]]=i;
  for(int i=1;i<=n;i++)cin>>b[i];
  cout<<n<<' ';up(1,1,n,1,pos[n],1);//第一次的答案肯定是n
  for(int i=1;i<n;i++){
    up(1,1,n,1,b[i],-1);//新加入一个炸弹
    while(!ge());
    cout<<ans<<' ';
  }
  return 0;
}