首页技术正文

AGC015 C-Nuske vs Phantom Thnook AtCoder 思路前缀和

开发者子骞技术 2022年11月14日

0 收藏 498 点赞 4,024 浏览 1206 个字

目录

[TOC]

题目链接

AGC015 C-Nuske vs Phantom Thnook AtCoder

题解

树的性质有:

如果每个蓝色连通块都是树，那么连通块个数=总点数−总边数。

二维前缀和维护点数和边数。

$O(nm + q)$

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#define gc getchar()
#define pc putchar
#define LL long long
inline int read() {
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9') c = gc;
while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();
return x * f;
}
void print(int x) {
if(x < 0) {
pc('-');
x = -x;
}
if(x >= 10) print(x / 10);
pc(x % 10 + '0');
}
const int maxn = 2010; int n,m,q;
int a[maxn][maxn];
int b[maxn][maxn],c[maxn][maxn];
char s[2007];
inline int calc(int a[maxn][maxn],int x1,int y1,int x2,int y2) {
    if(x1 > x2 || y1 > y2)  return 0;
    return a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1];
}
int main() {
n = read(),m = read(),q = read();
    for(int i = 1;i <= n;++ i) {
        scanf("%s",s + 1);
for(int j = 1;j <= m;++ j)
            a[i][j] = s[j] - '0';
    }
    for(int i = 2;i <= n;++ i)
        for(int j = 1;j <= m;++ j)
            b[i][j] = a[i][j] & a[i - 1][j];
    for(int i = 1;i <= n;++ i)
        for(int j = 2;j <= m;++ j)
            c[i][j] = a[i][j] & a[i][j - 1];
    for(int i = 1;i <= n;++ i)
        for(int j = 1;j <= m;++ j) {
            a[i][j] = a[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
            b[i][j] = b[i][j] + b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
            c[i][j] = c[i][j] + c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1];
    }
    while(q -- ) {
        int x1 = read(),y1 = read(),x2 = read(),y2 = read();
        print(calc(a,x1,y1,x2,y2) - calc(b,x1 + 1,y1,x2,y2) - calc(c,x1,y1 + 1,x2,y2));
        pc('\n');
    }
    return 0;
}