题目传送门
看到本题的时候,第一时间想到了区间查询和区间修改的二维树状数组,很明显,这样下去要变成火箭猫猫虫了(*゚∀゚*)
最后,还是在agKc学长的指导下,AC了本题
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
int dis[5] = {-1,0,1,0,-1};
int main()
{
cin.tie(nullptr)->sync_with_stdio(false);
int n,m;cin >> n >> m;
int q;cin >> q;
vector<vector<int> >num(n+1,vector<int>(m+1));
vector<int> a(n+1);
vector<int> b(m+1);
int t,x,y;
for(int i = 1;i<=q;i++) {
cin >> t >> x >> y;
if(t==1) {
if(x==1) {
a[y] = i;
}
else {
b[y] = i;
}
}
else {
num[x][y] = i;
for(int j = 0;j<4;j++) {
int sx = x+dis[j];int sy = y+dis[j+1];
if(sx>=1 && sx <=n && sy>=1 && sy<=m) {
num[sx][sy] = i;
}
}
}
}
ll ans = 0;
for(int i = 1;i<=n;i++) {
for(int j = 1;j<=m;j++) {
int cnt = num[i][j];
if(cnt && cnt>a[i] && cnt>b[j]) ans++;
}
}
cout << ans;
}
思路是这这样的,每次修改时,只修改纯白水汽的部分,保存红水汽的行和列,最后扫一遍的时候,比较最后是红水汽还是白水汽

京公网安备 11010502036488号