欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

CodeForces 1326E - Bombs

程序员文章站 2023-02-21 13:58:10
思维题杀我!现场$^ 2600$的状压DP都会做,$^ 2400$的思维题就不会了,看来是wtcl/ll "洛谷题目页面传送门" & "CodeForces题目页面传送门" 给定$2$个$1\sim n$的排列$a,b$。$a$上某些位置会存在炸弹。对于某些位置有炸弹的$a$,维护一个集合,初始为空 ......

思维题杀我!现场\(^*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;
}