ABC186 F - Rook on Grid 题解

zhln / 2024-09-26 / 原文

原题链接

Description

给定 $H$ 行 $W$ 列的格网，其中有 $M$ 个障碍，有一起点 $(1,1)$ ，可以横着或竖着走多个格子，求走两步以内可以达到的格子数。

Solution

显然我们先要维护：

$x[i]$ 表示第 $i$ 行第一个障碍的下标，若没障碍，则设为 $W+1$

$y[i]$ 表示第 $i$ 列第一个障碍的下标，若没障碍，则设为 $H+1$

那么容易统计答案：

对于第 $i$ 行，两步之内可以到达的格子数为 $x[i]-1$

对于第 $i$ 列，两步之内可以到达的格子数为 $y[i]-1$

接下来要考虑消去重复计算的格子。

对于上面两次统计，其实就是先往下走再往右走，和先往右走再往下走，假如我们已经统计完先下再右的个数，那么对于第 $i$ 列 $[1,y[i]-1]$ 的所有格子，若当前格子的左边有障碍的话，那么该格子只能由先右再下到达，反之，则该格子以及在第一次统计中对答案有贡献了。

因此，对于第二次统计，我们只需要当前列 $[1,y[i]-1]$ 的所有格子中左边有障碍的格子记录贡献，每统计完一列，就需要将该列中 $x[j]==i$ 的格子打上标记。这个过程显然可以用树状数组进行维护。

Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
using namespace std;
#define MAXN 200010
#define INF 0x3f3f3f3f
//#define int long long
int Read()
{
	int x=0,f=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=-f;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
	return x*f;
}
int n,h,w,t[MAXN];
int Lowbit(int x){return x&-x;}
void Add(int x,int val){for(;x<=h;x+=Lowbit(x))t[x]+=val;}
int Query(int x){int ans=0;for(;x;x-=Lowbit(x))ans+=t[x];return ans;}
int x[MAXN],y[MAXN];
vector<int> qwq[MAXN];
int main()
{
	h=Read();w=Read();n=Read();
	for(int i=1;i<=h;i++) x[i]=w+1;
	for(int i=1;i<=w;i++) y[i]=h+1;
	for(int i=1;i<=n;i++)
	{
		int ax=Read(),ay=Read();
		x[ax]=min(x[ax],ay);
		y[ay]=min(y[ay],ax);
	}
	long long ans=0;
	for(int i=1;i<=y[1]-1;i++) ans+=x[i]-1;
	for(int i=y[1];i<=h;i++) x[i]=1;
	for(int i=1;i<=h;i++) qwq[x[i]].push_back(i);
	for(int i=1;i<=w;i++)
	{
		if(y[i]==1) break;
//      cout<<i<<" "<<Query(y[i]-1)<<endl;
		ans+=Query(y[i]-1);
		for(int j=0;j<(int)qwq[i].size();j++)
			Add(qwq[i][j],1);
	}
	printf("%lld",ans);
	return 0;
}