图论+前缀和任(duty)

问题 B: 任(duty)
时间限制: 2 Sec 内存限制: 512 MB
题目描述
liu_runda退役之后就失去梦想开始咸鱼生活了…
Bilibili夏日画板活动中,所有人都可以在一块画板上进行像素画创作.UOJ群有一群无聊的人决定在画板上创作一个50*50的UOJ的LOGO.如下图.
这块画板实际上是很大的矩形网格.一个网格是一像素.
一个人每三分钟才能画一个像素.所以liu_runda的咸鱼生活非常无聊.
郭神表示他实在是看不下去liu_rudna这只颓狗了,于是随手出了一道神题,liu_runda不会做,于是给出到联考里了.
在画板上有一片黑白相间的矩形区域满足这样的性质:如果认为相同颜色的方块可以在上下左右四个方向连通,那么任意两个黑色方块要么不连通,要么连通但之间只有一条简单路径(不重复经过同一个格子的路径).
这个矩形区域有N行M列,从上到下依次为第1,2,3…N-1,N行,从左到右依次为第1,2,3…M-1,M列.
每次郭神会询问这片矩形区域内的一个子矩形.在只考虑这个子矩形内的像素时(即从子矩形内部不能和子矩形之外的像素相连通),问这个子矩形内的黑色方块组成了多少连通块.
如果不能完成这个任务,liu_runda就会被郭神批判一番…
【输入格式】

第一行三个整数N,M,Q,表示矩形区域有N行M列,有Q组询问.

接下来N行,每行一个长为M的01字符串.0表示白色,1表示黑色.第i行第j个字符表示第i行j列的颜色,

接下来Q行,每行4个整数x1,y1,x2,y2,(x1<=x2,y1<=y2)表示选出的矩形区域的两个对角.即选出一个左上角为第x1行第y1列,右下角为第x2行第y2列,包含x2-x1+1行,y2-y1+1列的区域.

【输出格式】

Q行,第i行一个整数ans表示第i组询问的答案.

【样例输入1】

3 4 4

1101

0110

1101

1 1 3 4

1 1 3 1

2 2 3 4

1 2 2 4

【样例输出1】

【样例输入2】

5 5 6

11010

01110

10101

11101

01010

1 1 5 5

1 2 4 5

2 3 3 4

3 3 3 3

3 1 3 5

1 1 3 4

【样例输出2】

【数据范围】

对于第1,2个测试点,Q=1

对于第3,4个测试点,N=1

对于第5,6,7个测试点,N=2

对于第8个测试点,N,M<=1000

对于第9个测试点,N,M<=1500

对于全部测试点,1<=N,M<=2000,1<=Q<=200000,1<=x1<=x2<=N,1<=y1<=y2<=M,保证任意两个黑色像素之间最多只有一条简单路径.

其实题面里还有张很无聊的图，懒得粘了。。
因为保证联通块里不存在环，只能由一条边互相连通，而同一联通块满足点数-边数==1；所以求出区间里所有点和所有边，相减即为答案。
因此我们可以维护前缀和。但有些细节。
举个样例（为了方便说我把0，1改成了点的标号）
1 2 3 4
5 6 7 8
9 0 10 11
比如我们要求7，8，10，11的，那么要把3-7，4-8，6-7，0-10的边都剪掉，因此会多剪掉7-10和7-8，所以得额外维护单列的值，把它加回去，具体就不细说了。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define N 2005
#define inf 1000000000
using namespace std;
int read()
{
    int sum=0,f=1;char x=getchar();
    while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
    while(x>='0'&&x<='9'){sum=(sum<<1)+(sum<<3)+x-'0';x=getchar();}
    return sum*f;
}
int n,m,q;
int a[2005][2005],dian[2005][2005],bian[2005][2005],h[2005][2005],z[2005][2005];
int l1,l2,r1,r2;
void init()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            dian[i][j]=dian[i][j-1]+a[i][j];
            bian[i][j]=bian[i][j-1];
            if(a[i][j]==1&&a[i][j-1]==1)bian[i][j]++;
            h[i][j]=bian[i][j];
        }
    for(int j=1;j<=m;j++)
        for(int i=1;i<=n;i++)
        {
            dian[i][j]+=dian[i-1][j];
            z[i][j]=z[i-1][j];
            if(a[i][j]==1&&a[i-1][j]==1)z[i][j]++;
        }
    for(int i=1;i<=n;i++)
    {
        int s=0;
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==1&&a[i-1][j]==1)s++;
            bian[i][j]+=bian[i-1][j]+s;
        }
    }
/*  for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            cout<<z[i][j]<<" ";
        cout<<endl;
    }*/
}
int main()
{
    n=read();m=read();q=read();
    char s[2005];
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        for(int j=1;j<=m;j++)
            a[i][j]=s[j]-'0';
    }
    init();int ans2,ans1;
    while(q--)
    {
        l1=read();r1=read();l2=read();r2=read();
        ans1=dian[l2][r2]-dian[l2][r1-1]-dian[l1-1][r2]+dian[l1-1][r1-1];
        ans2=bian[l2][r2]-bian[l2][r1]-bian[l1][r2]+bian[l1][r1];
        ans2+=z[l2][r1]-z[l1][r1]+h[l1][r2]-h[l1][r1];
        //cout<<ans1<<" "<<ans2<<endl;
        printf("%d
",ans1-ans2);
    }
}

图论+前缀和 任(duty)

图论+前缀和任(duty)