CodeForces 1326E - Bombs

思维题杀我！现场\(^*2600\)的状压dp都会做，\(^*2400\)的思维题就不会了，看来是wtcl/ll

洛谷题目页面传送门 & codeforces题目页面传送门

给定\(2\)个\(1\sim n\)的排列\(a,b\)。\(a\)上某些位置会存在炸弹。对于某些位置有炸弹的\(a\)，维护一个集合，初始为空，从左往右扫描整个排列\(a\)，每到一个位置上就将此位置上的数压进集合，若此位置有炸弹就把集合中最大的数弹出，我们称最终集合中最大的元素为\(a\)的结果。\(\forall i\in[0,n)\)，求若在\(\forall j\in[1,i],b_i\)这些位置放下炸弹，结果是多少。

\(n\in\left[1,3\times10^5\right]\)。

显然，依次算每个结果的话，第\(i\)次被弹出的集合是第\(i+1\)次被弹出的集合的子集，即今朝被弹出，永远就不会复活了。可以推出这\(n\)个结果非严格单调递减。于是我们可以two-pointers，维护目前最大的没有被弹出的数\(now\)，初始时\(now=n\)，每次算答案时不停地令\(now=now-1\)直到\(now\)没有被弹出。难点在于如何快速判断\(now\)是否被弹出。

如果真就一直在想\(now\)被弹出的充要条件，恭喜你，你被魔法杀死了。不难发现一个性质：无论何时，只要你正在考虑判断\(now\)是否被弹出，那么一定所有\(>now\)的数已经确认被弹出了（因为如果不是那样，\(now\)自减的过程就会在某个\(>now\)的数处停下）。于是我们所考虑的\(now\)被弹出，其实等价于所有\(\geq now\)的数都被弹出。这个东西的充要条件看上去容易探索一点（然鹅的确是这样）。

下面我们来探索所有\(\geq now\)的数都被弹出的充要条件。考虑每个\(\geq now\)的数\(a_x\)，显然对于每个在\(a_x\)右边且\(\geq now\)的数\(a_y\)（包括\(a_x\)自己），弹出它们的炸弹在\(a_y\)右边（包括\(a_y\)位置上），结合\(a_y\)在\(a_x\)右边可以得到弹出它们的炸弹一定在\(a_x\)右边（包括\(a_x\)位置上）。于是我们得到了所有在\(a_x\)右边且\(\geq now\)的数（包括\(a_x\)自己）都被弹出的一个很弱的必要条件：\(a_x\)右边的炸弹（包括\(a_x\)位置上）数量不低于在\(a_x\)右边且\(\geq now\)的数（包括\(a_x\)自己）的数量。充分性显然不满足。

不过，如果将\(\forall x(a_x\geq now)\)，所有在\(a_x\)右边且\(\geq now\)的数（包括\(a_x\)自己）都被弹出的这么多必要条件合并起来，得到所有\(\geq now\)的数都被弹出的一个必要条件：\(\forall x(a_x\geq now)\)，\(a_x\)右边的炸弹（包括\(a_x\)位置上的）数量不低于在\(a_x\)右边且\(\geq now\)的数（包括\(a_x\)自己）的数量。你会发现这个条件似乎很强，于是我们试图证明它的充分性。然后真就证出来了！

充分性证明（感性）：找到\(a_x=n\)，显然，\(a_x\)右边（包括\(a_x\)位置上）的最左边的炸弹与\(a_x\)匹配，于是我们可以想象将这个炸弹扔掉，并将\(a_x\)扔出排列，两边挨紧形成一个新的\(1\sim n-1\)的排列。\(a_x\)左边所有\(\geq now\)的数右边\(\geq now\)的数（包括自己）数量\(-1\)，右边的炸弹（包括自己位置上）数量\(-1\)；\(a_x\)右边、炸掉\(a_x\)的炸弹左边（包括炸弹位置上）所有\(\geq now\)的数，右边\(\geq now\)的数（包括自己）的数量不变，由于\(a_x\)与炸弹之间没有炸弹，所以它们右边的炸弹（包括自己位置上）数量至少剩\(a_x\)原来右边炸弹（包括自己位置上）的数量\(-1\)；炸弹右边所有\(\geq now\)的数右边\(\geq now\)的数（包括自己）的数量、炸弹（包括自己位置上）数量都没变。由此看来条件依然满足。于是原证明题可以转化为一个规模\(-1\)的证明题，可以用数学归纳法加以证明。

有了这个结论，接下来就好办了。设\(a_i\)右边\(\geq now\)的数（包括\(a_i\)自己）有\(grt_i\)个，右边的炸弹（包括\(a_i\)位置上）有\(bmb_i\)个。那么\(\forall x(a_x\geq now)\)，\(a_x\)右边的炸弹（包括\(a_x\)位置上的）数量不低于在\(a_x\)右边且\(\geq now\)的数（包括\(a_x\)自己）的数量，可以写成\(\forall x(a_x\geq now),bmb_x\geq grt_x\)，即\(\forall x(a_x\geq now),bmb_x-grt_x\geq0\)。于是我们需要维护\(\forall i\in[1,n],bmb_i-grt_i\)。判断\(now\)是否被弹出时只需判断全局最小值是否\(\geq0\)，每当\(now=now-1\)时（初始\(now=n\)时也要）就将位置\(a^{-1}_{now}\)上的\(bmb_{a^{-1}_{now}}-grt_{a^{-1}_{now}}\)激活（即今后算进全局最小值，激活之前懒标记可以帮忙保存\(bmb_{a^{-1}_{now}}-grt_{a^{-1}_{now}}\)）并令\(\forall i\in\left[1,a^{-1}_{now}\right],grt_i=grt_i+1\)，每当新增一个炸弹\(b_x\)就令\(\forall i\in[1,b_x],bmb_i=bmb_i+1\)。这只需要单点修改、区间增加、全局查询最小值的线段树即可实现。

下面是ac代码：

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int n=300000;
int n;//排列长度 
int a[n+1]/*排列*/,b[n+1]/*炸弹添加顺序*/;
int pos[n+1];//pos[i]为数i在a中的位置 
struct segtree{//线段树 
	struct node{int l,r,mn_dif/*此节点表示的区间内bmb[i]-grt[i]的最小值*/,lz/*蓝标记*/;}nd[n<<2];
	#define l(p) nd[p].l
	#define r(p) nd[p].r
	#define mn_dif(p) nd[p].mn_dif
	#define lz(p) nd[p].lz
	void bld(int l=1,int r=n,int p=1){//建树 
		l(p)=l;r(p)=r;mn_dif(p)=inf;/*一开始都是未激活状态*/lz(p)=0;
		if(l==r)return;
		int mid=l+r>>1;
		bld(l,mid,p<<1);bld(mid+1,r,p<<1|1);
	}
	void init(){bld();}//初始化 
	void sprup(int p){mn_dif(p)=min(mn_dif(p<<1),mn_dif(p<<1|1));}//上传节点信息 
	void sprdwn(int p){//下传懒标记 
		if(lz(p)){
			mn_dif(p<<1)+=lz(p);mn_dif(p<<1|1)+=lz(p);
			lz(p<<1)+=lz(p);lz(p<<1|1)+=lz(p);
			lz(p)=0;
		}
	}
	void on(int x,int p=1){//激活位置x 
		if(l(p)==r(p)){mn_dif(p)=lz(p)/*之前的bmb[l(p)]-grt[l(p)]保存在lz(p)里*/;return;}
		sprdwn(p);
		int mid=l(p)+r(p)>>1;
		on(x,p<<1|(x>mid));
		sprup(p);
	}
	void add(int l,int r,int v,int p=1){//区间增加 
		if(l<=l(p)&&r>=r(p)){mn_dif(p)+=v;lz(p)+=v;return;}
		sprdwn(p);
		int mid=l(p)+r(p)>>1;
		if(l<=mid)add(l,r,v,p<<1);
		if(r>mid)add(l,r,v,p<<1|1);
		sprup(p);
	}
	int _mn_dif(){return mn_dif(1);}//全局最小值 
}segt;
int main(){
	cin>>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];
	int now=n;//初始now=n 
	cout<<now<<" ";//不放炸弹时 
	segt.init();
	segt.on(pos[n]);
	segt.add(1,pos[n],-1);//增加一个>=now的数 
	for(int i=1;i<n;i++){
		segt.add(1,b[i],1);//增加一个炸弹 
		while(segt._mn_dif()>=0/*now被弹出*/){
			now--;
			segt.on(pos[now]);
			segt.add(1,pos[now],-1);//增加一个>=now的数 
		}
		cout<<now<<" ";
	}
	return 0;
}