题解 | #情人节的电灯泡#

思路

把n*n的矩阵摊平成一条直线，就可以用线段树的方法解决啦！
n<1000，所以展成直线就是1e6的单点修改+区间求和。
个人码风问题我全开ll了，第一发因为update写错了爆零（我太菜了）

代码

#include<stdio.h>
#include<iostream>
#include<cstring>
#define int ll
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
int tree[maxn*4],n,m,f,x1,x2,y1,y2;
bool num[maxn];

void build(int node,int start,int end){
    if(start==end){
        tree[node]=num[start];
        return;
    }
    int mid=start+end>>1;
    build(node<<1,start,mid);
    build(node<<1|1,mid+1,end);
    tree[node]=tree[node<<1]+tree[node<<1|1];
}

void update(int node,int start,int end,int id){
    if(start==end){
        tree[node]^=1;
        num[id]^=1;
        return;
    }
    int mid=(start+end)>>1;
    if(id<=mid) update(node<<1,start,mid,id);
    if(id>mid) update(node<<1|1,mid+1,end,id);
    tree[node]=tree[node<<1]+tree[node<<1|1];
}

int query(int node,int start,int end,int l,int r){
    if(l<=start&&end<=r) return tree[node];
    int mid=(start+end)>>1;
    int res=0;
    if(l<=mid) res+=query(node<<1,start,mid,l,r);
    if(r>mid) res+=query(node<<1|1,mid+1,end,l,r);
    return res;
}

signed main(){
    scanf("%lld%lld",&n,&m);
    int N=n*n;
    for(int i=0;i<n;i++)
        for(int j=1;j<=n;j++)
            scanf("%lld",&num[i*n+j]);
    build(1,1,N);
    for(int i=1;i<=m;i++){
        scanf("%lld",&f);
        if(f==1){
            scanf("%lld%lld",&x1,&y1);
            update(1,1,N,(x1-1)*n+y1);
        }else if(f==2){
            scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
            if(x1>x2) swap(x1,x2);
            if(y1>y2) swap(y1,y2);
            int ans=0;
            for(int j=x1;j<=x2;j++){
                ans+=query(1,1,N,(j-1)*n+y1,(j-1)*n+y2);
            }
            printf("%lld\n",ans);
        }
//        for(int i=1;i<=4*N;i++) cout<<tree[i]<<" ";
    }
    return 0;
}