1 条题解
-
0
每次相当于在一行操作一次，在列操作一次，如果一个格子的操作次数为奇数答案就会加一。
所以一个矩阵中的答案只需要统计有几行操作了奇数次，有几行操作了偶数次，和列的对应情况，直接用树状数组维护就好了。
代码
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; int n,m,_,a[N],b[N],c[2][N]; void add(int p,int x,int z){for(;x<=max(n,m);x+=x&-x)c[p][x]+=z;}//注意上界是max(n,m) int ask(int p,int x){int ans=0;for(;x;x-=x&-x)ans+=c[p][x];return ans;} int main(){ scanf("%d%d%d",&n,&m,&_); while(_--){ int T,x,y,xx,yy; scanf("%d",&T); if(T==1){ scanf("%d%d",&x,&y); a[x]^=1; if(a[x])add(0,x,1); else add(0,x,-1); b[y]^=1; if(b[y])add(1,y,1); else add(1,y,-1); } else{ scanf("%d%d%d%d",&x,&y,&xx,&yy); int sx1=ask(0,xx)-ask(0,x-1),sx0=(xx-x+1)-sx1; int sy1=ask(1,yy)-ask(1,y-1),sy0=(yy-y+1)-sy1; long long ans=1ll*sx1*sy0+1ll*sx0*sy1; printf("%lld\n",ans); } } }
- 1
