c/c++语言开发共享CodeForces 1326E – Bombs

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

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

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

(ninleft[1,3times10^5right])。

显然，依次算每个结果的话，第(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_xgeq now))，所有在(a_x)右边且(geq now)的数（包括(a_x)自己）都被弹出的这么多必要条件合并起来，得到所有(geq now)的数都被弹出的一个必要条件：(forall x(a_xgeq now))，(a_x)右边的炸弹（包括(a_x)位置上的）数量不低于在(a_x)右边且(geq now)的数（包括(a_x)自己）的数量。你会发现这个条件似乎很强，于是我们试图证明它的充分性。然后真就证出来了！

充分性证明（感性）：找到(a_x=n)，显然，(a_x)右边（包括(a_x)位置上）的最左边的炸弹与(a_x)匹配，于是我们可以想象将这个炸弹扔掉，并将(a_x)扔出排列，两边挨紧形成一个新的(1sim 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_xgeq now))，(a_x)右边的炸弹（包括(a_x)位置上的）数量不低于在(a_x)右边且(geq now)的数（包括(a_x)自己）的数量，可以写成(forall x(a_xgeq now),bmb_xgeq grt_x)，即(forall x(a_xgeq now),bmb_x-grt_xgeq0)。于是我们需要维护(forall iin[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 iinleft[1,a^{-1}_{now}right],grt_i=grt_i+1)，每当新增一个炸弹(b_x)就令(forall iin[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; }