AtCoder Beginner Contest 179 F.Simplified Reversi

AtCoder Beginner Contest 179 F.Simplified Reversi

题目链接

非常有趣的思维题~
假设黑色区域宽为 $x$，长为 $y$，我们考虑一种修改，比如 $1,k$，此时不难发现修改后对 $[k+1,y]$ 的 $1$ 操作，都是固定的减去 $x$，所以这是一种典型的缩小策略，每操作一次都将黑色区域的长宽进行缩小，并用数组记录减少的黑色方块数即可，AC代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,x,y,q,op,k,r[N],c[N];
int main(){cin>>n>>q;x=y=n;ll ans=(n-2LL)*(n-2LL);while(q--){cin>>op>>k;if(op==1) {if (k < y) {ans -= x - 2;while (y > k) c[y--] = x - 2;} else ans -= c[k];}else{if (k < x) {ans -= y - 2;while (x > k) r[x--] = y - 2;} else ans -= r[k];}}cout<<ans;return 0;
}