Holiday Painting

* 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: $R1_i, R2_i, C1_i, C2_i,$ and $X_i$

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

C++11(clang++ 3.9) 解法, 执行用时: 184ms, 内存消耗: 24536K, 提交时间: 2019-08-04 11:28:26

/*
	m每一列维护一个线段树
	复杂度就是 15*n*logn 
	记录区间白色或者黑色的数量
	每次修改的时候就可以 根据修改颜色进行sum计算
	 白0     黑1 
*/
#include<bits/stdc++.h> 
#define ll long long
#define lc (rt<<1)
#define rc (rt<<1|1)
#define mid ((l+r)>>1)
using namespace std;
const int N=5e4+50;
bool a[N][16];
struct tree
{
	int sum[N<<2],lazy[N<<2],w[N<<2];
	void up(int rt) {sum[rt]=sum[lc]+sum[rc];} 
	void build(int rt,int l,int r,int k)
	{
		if(l==r) {sum[rt]=w[rt]=!a[l][k];lazy[rt]=-1; return ;}
		build(lc,l,mid,k),build(rc,mid+1,r,k),up(rt);
		w[rt]=w[lc]+w[rc]; 
	}
	void down(int rt,int len)
	{
		if(lazy[rt]==-1) return ;
		if(!lazy[rt]) sum[lc]=w[lc],sum[rc]=w[rc];
		else sum[lc]=(len-(len>>1))-w[lc],sum[rc]=(len>>1)-w[rc];
		lazy[lc]=lazy[rc]=lazy[rt]; lazy[rt]=-1;
	}
	void work(int rt,int l,int r,int L,int R,int col)
	{
		if(L<=l&&r<=R)
		{
			if(!col) sum[rt]=w[rt];
			else sum[rt]=r-l+1-w[rt];
			lazy[rt]=col; return;
		}
		down(rt,r-l+1);
		if(L<=mid) work(lc,l,mid,L,R,col);
		if(R>mid) work(rc,mid+1,r,L,R,col); up(rt);
	}
} T[16];
int main()
{
	int r,c,n; char s[20];
	scanf("%d%d%d",&r,&c,&n); 
	for(int i=1;i<=r;i++)
	{
		scanf("%s",s+1);
		for(int j=1;j<=c;j++)
			a[i][j]=(s[j]=='1');
	}
	for(int i=1;i<=c;i++) T[i].build(1,1,r,i);
	while(n--)
	{
		int r1,r2,c1,c2,col;
		scanf("%d%d%d%d%d",&r1,&r2,&c1,&c2,&col);
		for(int i=c1;i<=c2;i++) T[i].work(1,1,r,r1,r2,col);
		int res=0; for(int i=1;i<=c;i++) res+=T[i].sum[1];
		printf("%d\n",res);
	}
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 182ms, 内存消耗: 34424K, 提交时间: 2019-08-04 16:06:38

#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define lc (t<<1)
#define rc ((t<<1)|1)
int ans,n,m,q,r1,r2,c1,c2,p,l[210000],r[210000],mi[210000],f[16][210000],c[16][210000][2],bz[16][210000];
char s[60000][16];
inline void up(int t){
	fo(i,c1,c2){
		c[i][t][0]=c[i][lc][0]+c[i][rc][0];
		c[i][t][1]=c[i][lc][1]+c[i][rc][1];
		f[i][t]=f[i][lc]+f[i][rc];
	}
}
inline void down(int t){
	fo(i,c1,c2)
		if (bz[i][t]){
			bz[i][lc]=bz[i][rc]=bz[i][t];
			f[i][lc]=c[i][lc][bz[i][t]-1];
			f[i][rc]=c[i][rc][bz[i][t]-1];
			bz[i][t]=0;
		}
}
void buildt(int t,int x,int y){
//	printf("%d %d %d\n",t,x,y);
	l[t]=x;
	r[t]=y;
	if (x<y){//l<r!!!!!!
		mi[t]=(x+y)>>1;
		buildt(lc,x,mi[t]);
		buildt(rc,mi[t]+1,y);
		up(t);
	}else{
		fo(i,1,m){
			c[i][t][s[x][i]-'0']++;
			f[i][t]=c[i][t][0];
		}
	}
}
void chang(int t,int x,int y){
	if (x==l[t]&&y==r[t]){
		fo(i,c1,c2){
			bz[i][t]=p+1;
			f[i][t]=c[i][t][p];
		}
		return;
	}
	down(t);
	if (y<=mi[t]) chang(lc,x,y);else if (x>mi[t]) chang(rc,x,y);else{
		chang(lc,x,mi[t]);
		chang(rc,mi[t]+1,y);
	}
	up(t);
}
int main(){
	scanf("%d%d%d",&n,&m,&q);
	fo(i,1,n) scanf("%s",s[i]+1);
	c1=1;c2=m;
	buildt(1,1,n);
	while (q--){
		scanf("%d%d%d%d%d",&r1,&r2,&c1,&c2,&p);
		chang(1,r1,r2);
		ans=0;
		fo(i,1,m) ans+=f[i][1];
		printf("%d\n",ans);
	}
	return 0;
}

详情