【2019.8.12 慈溪模拟赛 T2】汪哥图（wang）（前缀和）

森林

考虑到题目中给出条件两点间至多只有一条路径。

就可以发现，这是一个森林。

而森林有一个很有用的性质。

考虑对于一棵树，点数-边数=\(1\)。

因此对于一个森林，点数-边数=连通块个数。

所以，我们只要前缀和求出询问区间内的点数和边数，就可以计算出连通块个数了。

注意边数要分两个方向讨论，然后询问时注意防止越界。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 2000
using namespace std;
int n,m,Qt,a[N+5][N+5];
class FastIO
{
    private:
        #define FS 100000
        #define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
        #define pc(c) (C==E&&(clear(),0),*C++=c)
        #define tn (x<<3)+(x<<1)
        #define D isdigit(c=tc())
        int T;char c,*A,*B,*C,*E,FI[FS],FO[FS],S[FS];
    public:
        I FastIO() {A=B=FI,C=FO,E=FO+FS;}
        Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}
        Tp I void readD(Ty& x) {W(!D);x=c&15;}
        Tp I void write(Ty x) {W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);}
        Tp I void writeln(Con Ty& x) {write(x),pc('\n');}
        I void clear() {fwrite(FO,1,C-FO,stdout),C=FO;}
}F;
class SuffixSumSolver
{
    private:
        int d[N+5][N+5],e1[N+5][N+5],e2[N+5][N+5];
    public:
        I void Solve()
        {
            RI i,j,xx,yx,xy,yy,td,te1,te2;for(i=1;i<=n;++i) for(j=1;j<=m;++j)//预处理前缀和
                d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+a[i][j],//点数
                e1[i][j]=e1[i-1][j]+e1[i][j-1]-e1[i-1][j-1]+(a[i][j]&a[i-1][j]),//向上的边
                e2[i][j]=e2[i-1][j]+e2[i][j-1]-e2[i-1][j-1]+(a[i][j]&a[i][j-1]);//向左的边
            W(Qt--) F.read(xx),F.read(yx),F.read(xy),F.read(yy),//处理询问
                td=d[xy][yy]-d[xx-1][yy]-d[xy][yx-1]+d[xx-1][yx-1],//点数
                te1=e1[xy][yy]-e1[xx][yy]-e1[xy][yx-1]+e1[xx][yx-1],//向上的边，最上面一行不能选
                te2=e2[xy][yy]-e2[xx-1][yy]-e2[xy][yx]+e2[xx-1][yx],//向左的边，最左边一列不能选
                F.writeln(td-te1-te2);//点数-边数=连通块个数
        }
}S;
int main()
{
    freopen("wang.in","r",stdin),freopen("wang.out","w",stdout);
    RI i,j;F.read(n),F.read(m),F.read(Qt);
    for(i=1;i<=n;++i) for(j=1;j<=m;++j) F.readD(a[i][j]);
    return S.Solve(),F.clear(),0;
}

【2019.8.12 慈溪模拟赛 T2】汪哥图（wang）（前缀和）

原文：https://www.cnblogs.com/chenxiaoran666/p/Contest20190812T2.html