题解 | Holiday-牛客假日团队赛9J题

输入描述:

观察到列数只有15,可以想到对于每一列维护一颗线段树

sum表示该区间与目标矩阵中该区间相同元素个数

lazy表示该区间应被修改成什么颜色

g即目标矩阵中该区间白色格子的个数

显然一个区间的sum=区间长度-g(修改为0时) 或 g(修改为1时)

#define RG register
#include<cstdio>
using namespace std;
const int N=50005;
int n,m,q,X,Ans;
int a[N][16];
inline int read()
{
    RG int x=0,w=1;RG char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*w;
}
struct segment{
    int sum[N<<2],lazy[N<<2],g[N<<2];
    inline void Pushup(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];}
    void Build(int rt,int l,int r,int k){
        if(l==r)
        {
            sum[rt]=a[l][k]^1;
            g[rt]=a[l][k];
            return;
        }
        int mid=(l+r)>>1;
        Build(rt<<1,l,mid,k);
        Build(rt<<1|1,mid+1,r,k);
        Pushup(rt);
        g[rt]=g[rt<<1]+g[rt<<1|1];
    }
    inline void Pushdown(int rt,int s){//s即区间长度
        int t=lazy[rt];
        if(t==-1)return;
        if(!t)
        {
            sum[rt<<1]=(s-(s>>1))-g[rt<<1];
            sum[rt<<1|1]=(s>>1)-g[rt<<1|1];
        }
        else
        {
            sum[rt<<1]=g[rt<<1];
            sum[rt<<1|1]=g[rt<<1|1];
        }
        lazy[rt<<1]=lazy[rt<<1|1]=t;
        lazy[rt]=-1;
    }
    void Modify(int rt,int l,int r,int ll,int rr){
        if(ll<=l&&r<=rr)
        {
            if(X)sum[rt]=g[rt];
            else sum[rt]=r-l+1-g[rt];
            lazy[rt]=X;
            return;
        }
        Pushdown(rt,r-l+1);
        int mid=(l+r)>>1;
        if(ll<=mid)Modify(rt<<1,l,mid,ll,rr);
        if(rr>mid)Modify(rt<<1|1,mid+1,r,ll,rr);
        Pushup(rt);
    }
}T[16];
int main()
{
    n=read();
    m=read();
    q=read();
    RG char c;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            c=getchar();
            while(c!='0'&&c!='1')c=getchar();
            a[i][j]=c-'0';
        }
    for(int i=1;i<=m;i++)T[i].Build(1,1,n,i);
    RG int x1,x2,y1,y2;
    while(q--)
    {
        x1=read();
        x2=read();
        y1=read();
        y2=read();
        X=read();
        for(int i=y1;i<=y2;i++)T[i].Modify(1,1,n,x1,x2);
        Ans=0;
        for(int i=1;i<=m;i++)Ans+=T[i].sum[1];
        printf("%d\n",Ans);
    }
    return 0;
}