526互联

「Gym102759B」Cactus Competition 题解

发布时间 2023-03-25 11:11:46作者: zsc985246

传送门

「Gym102759B」Cactus Competition

题目大意

有一个 \(n \times m\) 的网格图，一个长度为 \(n\) 的序列 \(a\)，和一个长度为 \(m\) 的序列 \(b\)。

网格图中，第 \(i\) 行第 \(j\) 列的位置有一个数 \(c_{i,j}=a_i+b_j\)。\(c_{i,j} \ge 0\) 表示这个位置可以通过。

一对 \((S,T)\) 合法当且仅当 \(S \le T\)，点 \((S,1)\) 作为起点，\((T,m)\) 作为终点，只向下走或向右走能从起点到达终点。

求合法的 \((S,T)\) 总数。

\(n,m \le 2 \times 10^5\)。

思路

由于 \(n,m\) 很大，而且题目给出 \(c\) 数组的方式很特殊，我们考虑这个图有什么性质。

首先，我们考虑从 \((1,1)\) 到 \((n,m)\) 怎么走。

对于一般的图，有可能会有下图情况，其中灰色的是不能走的位置：

图挂了

回到本题的图中，我们可以发现，因为 \(c_{i,j}=a_i+b_j,c_{i+1,j}=a_{i+1}+b_j\)，又由图知 \(c_{i+1,j} < 0,c_{i,j} \ge 0\)，所以 \(c_{i,j} > c_{i+1,j}\)，也就是 \(a_i > a_{i+1}\)。

根据 \(a_i > a_{i+1}\) 倒推得 \(c_{i,j+1} > c_{i+1,j+1}\)，所以 \((i+1,j+1)\) 必定是不能走的。

那么拓展到一般情况，只要存在一个 \(x\) 使得 \((i,x)\) 能走，\((i+1,x)\) 不能走，那么对于任意的 \(x\)，\((i,x)\) 不能走时 \((i+1,x)\) 必定不能走。

举个例子，下图所有橙色的位置都是不能走的。

图挂了

竖着的不能走的段同理。

所以在本题中从 \((1,1)\) 到 \((n,m)\) 没有路只有四种情况：

  1. 有一整行不能走，即 \(\exists x \in [1,n]\)，使得 \(\forall y \in [1,m],a_x+b_y < 0\)；

  2. 有一整列不能走，即 \(\exists y \in [1,m]\)，使得 \(\forall x \in [1,n],a_x+b_y < 0\)；

  3. 不能走的位置将 \((1,1)\) 围住了，即 \(\exists x \in [1,n],y \in [1,m]\)，使得 \(\forall i \in [1,x],a_i+b_y < 0\) 且 \(\forall j \in [1,y],a_x+b_j < 0\)；

  4. 不能走的位置将 \((n,m)\) 围住了，即 \(\exists x \in [1,n],y \in [1,m]\)，使得 \(\forall i \in [x,n],a_i+b_y < 0\) 且 \(\forall j \in [y,m],a_x+b_j < 0\)。

现在我们找到了图的性质，回归原来的问题，不固定起终点，考虑对这四种情况分别如何计算答案。

直接计算不太好想，我们考虑计算不合法的数量。按照不合法的四种情况进行讨论：

  1. 令第 \(i\) 行不能走，那么 \(S \in [1,i],T \in [i,n]\) 不合法。

  2. 令第 \(j\) 列的 \(l\) 行到 \(r\) 行之间不能走，那么 \(S \in [l,r],T \in [l,r]\) 不合法。

  3. 令不能走的位置的交叉处坐标为 \((i,j)\)，最上方的不能走的格子纵坐标为 \(t\)，那么 \(S \in [t,j],T \in [t,n]\) 不合法。

  4. 令不能走的位置的交叉处坐标为 \((i,j)\)，最下方的不能走的格子纵坐标为 \(t\)，那么 \(S \in [1,t],T \in [j,t]\) 不合法。

我们发现，每种情况都是对 \(S,T\) 做出了限制，直接乘起来会计算重复，所以可以根据套路，将其转化为矩形面积，使用扫描线处理。

套路：两个变量同时受到限制，答案用到这两个变量的乘积，且直接算会算重的时候，可以使用扫描线。

但是这里需要注意 \(S \le T\)。这个的处理方法有两种，一种是查询时只查绿色部分；一种是暴力加 \(n\) 个阶梯状的蓝色矩形。代码中使用的是后者。

图挂了

最后，我们需要使用二分、ST 表和前后缀最值来加快处理速度，具体实现见代码。

总复杂度 \(O(n \log n)\)。

注意把数组大小算对！代码中的数组是卡范围开的，可以用作参考。

代码实现

小提示： y1 不能用作全局变量名。

#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(ll i=(a);i<=(b);++i)
#define Rep(i,a,b) for(ll i=(a);i>=(b);--i)
const ll N=2e5+10;
using namespace std;

struct node{
	ll x,y1,y2;//位置
	ll opt;//类型
}line[N*8];//线段
ll cnt;//线段个数
bool cmp(node a,node b){//按x坐标排序
	return a.x<b.x;
}

struct ST{//ST表
	ll log[N];
	ll f[N][20];
	void init(ll n,ll a[]){//预处理
		log[0]=-1;
		For(i,1,n)log[i]=log[i>>1]+1,f[i][0]=a[i];
		For(j,1,log[n]){
			For(i,1,n-(1<<j)+1){
				f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
			}
		}
	}
	ll query(ll l,ll r){//查询
		if(l>r)return 1145141919810;
		ll t=log[r-l+1];
		return max(f[l][t],f[r-(1<<t)+1][t]);
	}
}ST_a;

struct SEG{//线段树
	#define lson rt<<1
	#define rson rt<<1|1
	ll tot[N*32],lazy[N*32];
	void pushup(ll rt,ll l,ll r){
		if(lazy[rt]>0)tot[rt]=r-l+1;
		else tot[rt]=tot[lson]+tot[rson];
	}
	void change(ll rt,ll l,ll r,ll x,ll y,ll z){
		if(x<=l&&r<=y){
			lazy[rt]+=z;
			pushup(rt,l,r);
			return;
		}
		ll mid=l+r>>1;
		if(x<=mid)change(lson,l,mid,x,y,z);
		if(y>mid)change(rson,mid+1,r,x,y,z);
		pushup(rt,l,r);
	}
}seg;

ll n,m,k,q;
ll a[N];
ll b[N];
ll pmin[N],pmax[N];//前缀最值
ll smin[N],smax[N];//后缀最值

void add(ll x1,ll x2,ll y1,ll y2){//将矩形转化为线段
	if(x1>x2||y1>y2)return;
	x2++;
	line[++cnt]=(node){x1,y1,y2,1};
	line[++cnt]=(node){x2,y1,y2,-1};
}

void mian(){
	
	scanf("%lld",&n);
	scanf("%lld",&m);
	For(i,1,n){
		scanf("%lld",&a[i]);
	}
	For(i,1,m){
		scanf("%lld",&b[i]);
	}
	//最值预处理
	ST_a.init(n,a);
	pmax[0]=smax[m+1]=-1e9;
	pmin[0]=smin[m+1]=1e9;
	For(i,1,m){
		pmax[i]=max(pmax[i-1],b[i]);
		pmin[i]=min(pmin[i-1],b[i]);
	}
	Rep(i,m,1){
		smax[i]=max(smax[i+1],b[i]);
		smin[i]=min(smin[i+1],b[i]);
	}
	//1. 一整行不能走
	For(i,1,n){
		if(a[i]+pmax[m]<0){
			add(1,i,i,n);
		}
	}
	//2. 一列的一段连续区间不能走
	For(j,1,m){
		if(b[j]==pmin[m]){//只需要找最小位置
			ll l=1,r=1;
			while(l<=n){
				while(a[r]+b[j]<0&&r<=n)r++;
				add(l,r-1,l,r-1);
				l=r=r+1;
			}
			break;
		}
	}
	//3. 一个边框把起点围住了
	For(i,1,n){
		ll l,r;
		//二分找出最右端位置
		l=1,r=m;
		ll j=0;
		while(l<=r){
			ll mid=l+r>>1;
			if(pmax[mid]+a[i]<0)l=mid+1,j=mid;
			else r=mid-1;
		}
		if(!j)continue;
		//二分找出最大长度
		l=1,r=i;
		ll t=i;
		while(l<=r){
			ll mid=l+r>>1;
			if(pmin[j]+ST_a.query(mid,i)<0)r=mid-1,t=mid;
			else l=mid+1;
		}
		add(t,i,t,n);
	}
	//4. 一个边框把终点围住了
	For(i,1,n){
		ll l,r;
		//二分找出最左端位置
		l=1,r=m;
		ll j=m+1;
		while(l<=r){
			ll mid=l+r>>1;
			if(smax[mid]+a[i]<0)r=mid-1,j=mid;
			else l=mid+1;
		}
		if(j>m)continue;
		//二分找出最大长度
		l=i,r=n;
		ll t=i;
		while(l<=r){
			ll mid=l+r>>1;
			if(smin[j]+ST_a.query(i,mid)<0)l=mid+1,t=mid;
			else r=mid-1;
		}
		add(1,t,i,t);
	}
	//添加阶梯状矩阵
	For(i,1,n)add(i,i,1,i-1);
	//排序
	sort(line+1,line+cnt+1,cmp);
	//扫描线
	ll ans=0;
	For(i,1,cnt){
		if(i>1)ans+=(line[i].x-line[i-1].x)*seg.tot[1];
		seg.change(1,1,n,line[i].y1,line[i].y2,line[i].opt);
	}
	//总体减去不合法
	printf("%lld",n*n-ans);
	
}

int main(){
	int T=1;
//	scanf("%d",&T);
	while(T--)mian();
	return 0;
}

尾声

如果你发现了问题，你可以直接回复这篇题解

如果你有更好的想法，也可以直接回复！