ABC186 F - Rook on Grid 题解

原题链接

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;
}