考场上的一点分析
依次加入炸弹的过程中，每个炸弹会匹配到原序列的一个值——也就是它要炸掉的值。但是因为炸弹不是按位置顺序加入的，所以在加入的过程中，炸弹和值的匹配关系会发生变化，而这个变化会产生连锁反应，不好快速维护。（例如样例二中就可以看出这种匹配关系的变化）
题解
换个角度思考。容易发现答案是单调不增的。所以我们可以把问题转化为，判断当前答案是否小于某个值(x)。
也就是说，我们需要炸掉所有(geq x)的值。
- 考虑最右边的(geq x)的值，它右边必须至少有一个炸弹。
- 右起第二个(geq x)的值，它右边必须至少有两个炸弹。
- ......
- 右起第(k)个(geq x)的值，它右边必须至少有(k)个炸弹。
考虑构造一个序列(b_i)，表示(idots n)中(geq x)的值的数量 减去 炸弹的数量。
发现答案小于(x)当且仅当所有(b_i)都(leq0)。也就是说每个(geq x)的值，都能被至少一个炸弹“照顾”到。
用线段树维护(b)序列，支持区间加、求全局最大值即可。
时间复杂度(O(nlog n))。
总结
发现了答案的单调性后，我们把问题转化为：判断当前答案是否小于某个值(x)。这有点像二分答案，这样做的好处是：所有需要被炸掉的值都是确定的了。我们只要判断能否把它们都炸掉即可。
代码
参考代码：
//problem:CF1326E
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fst first
#define scd second
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
namespace Fread{
const int MAXN=1<<20;
char buf[MAXN],*S,*T;
inline char getchar(){
if(S==T){
T=(S=buf)+fread(buf,1,MAXN,stdin);
if(S==T)return EOF;
}
return *S++;
}
}//namespace Fread
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#endif
inline int read(){
int f=1,x=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline ll readll(){
ll f=1,x=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
/* ------ by:duyi ------ */ // myt天下第一
const int MAXN=3e5;
int n,a[MAXN+5],q[MAXN+5],pos[MAXN+5];
struct SegmentTree{
int val[MAXN*4+5],tag[MAXN*4+5];
void push_down(int p){
if(tag[p]){
val[p<<1]+=tag[p];
tag[p<<1]+=tag[p];
val[p<<1|1]+=tag[p];
tag[p<<1|1]+=tag[p];
tag[p]=0;
}
}
void push_up(int p){
val[p]=max(val[p<<1],val[p<<1|1]);
}
void modify(int p,int l,int r,int ql,int qr,int v){
if(ql<=l && qr>=r){
val[p]+=v;
tag[p]+=v;
return;
}
push_down(p);
int mid=(l+r)>>1;
if(ql<=mid)modify(p<<1,l,mid,ql,qr,v);
if(qr>mid)modify(p<<1|1,mid+1,r,ql,qr,v);
push_up(p);
}
SegmentTree(){}
}T;
int main() {
n=read();
for(int i=1;i<=n;++i)a[i]=read(),pos[a[i]]=i;
for(int i=1;i<=n;++i)q[i]=read();
int ans=n;
T.modify(1,1,n,1,pos[n],1);
for(int i=1;i<=n;++i){
printf("%d ",ans);
T.modify(1,1,n,1,q[i],-1);
if(i==n)break;
while(1){
assert(ans>=1);
if(T.val[1]<=0){
--ans;
T.modify(1,1,n,1,pos[ans],1);
}
else break;
}
}
puts("");
return 0;
}