题目描述

To show their spirit for the holidays, the cows would like to paint a picture! Their picture will be represented as an R x C () grid of unit squares, each of which is either 0 or 1. The grid rows are conveniently numbered 1..R; the columns are numbered 1..C.
Being pressed for time, the cows have asked their neighbors north of the border for help. Under the very helpful supervision of Canmuu the moose, they constructed a machine to throw paint at the picture in entire buckets! Beginning with all 0's in the picture grid, the machine splashes a certain paint color (either 0 or 1) over a rectangle in the grid. In particular, Canmuu suggested that they perform Q () operations; operation i consists of five integers and (), meaning that the cows will paint each unit square with a row index between and , inclusive, and a column index between and , inclusive, with color .
However, painting a picture like this is quite prone to mistakes. So Canmuu has enlisted you to determine, after each operation, the number of unit squares in the grid which are the correct color.

输入描述:

* Line 1: Three space-separated integers: R, C, and Q
* Lines 2..R+1: Line i+1 contains C characters, each '0' or '1', denoting the i-th row of the grid in the obvious way.
* Lines R+2..R+Q+1: Line R+i+1 contains five space-separated integers representing a paint operation:  and 

输出描述:

* Lines 1..Q: On line i+1, print a single integer representing the number of matching unit squares after the i-th operation.

示例1

输入
17 15 10 
111111101111111 
111111000111111 
111110000011111 
111100000001111 
111000000000111 
111100000001111 
111000000000111 
110000000000011 
111000000000111 
110000000000011 
100000000000001 
110000000000011 
100000000000001 
000000000000000 
111111000111111 
111111000111111 
111111000111111 
5 8 2 14 1 
8 17 3 7 1 
4 5 10 15 0 
7 16 12 14 1 
2 17 13 14 0 
2 6 2 3 1 
13 14 4 8 1 
3 6 6 7 1 
1 16 10 11 0 
7 16 10 10 0 
输出
113
94
95
91
87
93
91
87
93
93
说明
After the first operation, the picture grid looks as follows:
000000000000000
000000000000000
000000000000000
000000000000000
011111111111110
011111111111110
011111111111110
011111111111110
000000000000000
000000000000000
000000000000000
000000000000000
000000000000000
000000000000000
000000000000000
000000000000000
000000000000000
There are 113 unit squares which match the corresponding square in
the tree image; they are denoted below by an 'x' (the other bits
are shown as they appear after the first paint splash):
0000000x0000000
000000xxx000000
00000xxxxx00000
0000xxxxxxx0000
0xx111111111xx0
0xxx1111111xxx0
0xx111111111xx0
0x11111111111x0
000xxxxxxxxx000
00xxxxxxxxxxx00
0xxxxxxxxxxxxx0
00xxxxxxxxxxx00
0xxxxxxxxxxxxx0
xxxxxxxxxxxxxxx
000000xxx000000
000000xxx000000
000000xxx000000

解答

观察到列数只有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;
}


来源：中国飞鱼