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