CodeForces 1326E – Bombs

0
11

思维题杀我!现场\(^*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\)时也要)就将位置\(\left(a^{-1}\right)_{now}\)上的\(bmb_{\left(a^{-1}\right)_{now}}-grt_{\left(a^{-1}\right)_{now}}\)激活(即今后算进全局最小值,激活之前懒标记可以帮忙保存\(bmb_{\left(a^{-1}\right)_{now}}-grt_{\left(a^{-1}\right)_{now}}\))并令\(\forall i\in\left[1,\left(a^{-1}\right)_{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;
}

<

发布回复

请输入评论!
请输入你的名字