Luogu P3801 红色的幻想乡

解析

• 首先想到暴力解法，开二维数组 e[i][j] 表示 (i,j) 点的状态，e[i][j]=1 表示该点有红雾，e[i][j]=0 则没有红雾，每次修改状态时只需让其 $ \bigoplus 1 $ 即可
• 我们知道每个点若被修改奇数次则它是红雾，被修改偶数次则不是红雾，所以考虑容斥
• 对每一行、每一列分别处理，因为每次修改会修改一行和一列，所以对每一行和每一列记录它被修改的次数，被修改奇数次为 1 ，偶数次为 0 ，然后询问时需要找出被询问矩阵中行为 1 的个数和列为 1 的个数再进行容斥处理，所以用到线段树，对行和列分别建树，修改和询问操作就简单了

• 答案的计算有两种方法：

  1.直接计算红雾点个数：标记为 1 的行的个数和标记为 0 的列的个数的乘积 + 标记为 0 的行的个数和标记为 1 的列的个数的乘积
  2.间接计算红雾点个数：被询问矩阵内点的总个数 - 标记为 1 的行和列的个数的乘积 - 标记为 0 的行和列的个数的乘积

Code

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int N=1e5+5;
struct seg_tree
{
    LL str[N<<2];
    void pushup(int root)
    {
        str[root]=str[root*2]+str[root*2+1];
        return;
    }
    void build(int root,int l,int r)
    {
        if(l==r)
        {
            str[root]=0;
            return;
        }
        int mid=(l+r)>>1;
        build(root*2,l,mid);
        build(root*2+1,mid+1,r);
        pushup(root);
        return;
    }
    void update(int root,int l,int r,int u,int w)
    {
        if(l==r)
        {
            str[root]^=w;
            return;
        }
        int mid=(l+r)>>1;
        if(mid>=u) update(root*2,l,mid,u,w);
        if(mid<u) update(root*2+1,mid+1,r,u,w);
        pushup(root);
        return;
    }
    LL query(int root,int l,int r,int ll,int rr)
    {
        if(ll<=l&&r<=rr) return str[root];
        LL res=0;
        int mid=(l+r)>>1;
        if(mid>=ll) res+=query(root*2,l,mid,ll,rr);
        if(mid<rr) res+=query(root*2+1,mid+1,r,ll,rr);
        return res;
    }
}strh,strl;
int n,m,q;
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    strh.build(1,1,n);
    strl.build(1,1,m);
    while(q--)
    {
        int opt;
        scanf("%d",&opt);
        if(opt==1)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            strh.update(1,1,n,x,1);
            strl.update(1,1,m,y,1);
        }
        if(opt==2)
        {
            int x1,y1,x2,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            int hs=x2-x1+1,ls=y2-y1+1;
            int sh=strh.query(1,1,n,x1,x2);
            int sl=strl.query(1,1,m,y1,y2);
            LL ans=1ll*sh*(ls-sl)+1ll*(hs-sh)*sl;//直接求有红雾的点的个数 
//          LL ans=1ll*hs*ls-1ll*sh*sl-1ll*(hs-sh)*(ls-sl);//通过总个数-没有红雾的点的个数 
            printf("%lld\n",ans);
        }
    }
    return 0;
}

Luogu P3801 红色的幻想乡

原文：https://www.cnblogs.com/Hawking-llfz/p/11586562.html