题解：AT_tkppc3_d 巨大チェスボード

显然可以把这个网格看成

H \times W

的二维数组，数组的值为一个格子的面积，然后前缀和就能拿到部分分。

要做到满分，需要一种更高效的计算面积的方式。考虑样例：

计算 1 1 3 2 的答案。我们可以发现，黑色部分的面积

=14 \times (7+5)+9 \times 35

，也就是这个区间上边缘黑色的长度乘上这个区间左边缘黑色的长度，再加上它上边缘白色的长度乘上左边缘白色的长度。

用前缀和记录行和列的数字总和和黑色部分的总和就行了。

CPP

#include <cstdio>

#define ll long long
const int maxH=1e5+5;
int H,W,Q;
ll a[maxH],b[maxH],ba[maxH],bb[maxH];
int main(){
    scanf("%d%d%d",&H,&W,&Q);
    for(int i=1;i<=H;i++)
        scanf("%lld",&a[i]),ba[i]=ba[i-1]+(i&1)*a[i],a[i]+=a[i-1];
    for(int i=1;i<=W;i++)
        scanf("%lld",&b[i]),bb[i]=bb[i-1]+(i&1)*b[i],b[i]+=b[i-1];
    while(Q--){
        int px,py,qx,qy;
        scanf("%d%d%d%d",&px,&py,&qx,&qy);
        ll all=(a[qx]-a[px-1])*(b[qy]-b[py-1]);
        ll black1=(ba[qx]-ba[px-1])*(bb[qy]-bb[py-1]);
        ll black2=((a[qx]-a[px-1])-(ba[qx]-ba[px-1]))*((b[qy]-b[py-1])-(bb[qy]-bb[py-1]));
        printf("%lld\n",black1+black2-(all-black1-black2));
    }
    return 0;
}

题解：AT_tkppc3_d 巨大チェスボード

文章操作

相关推荐

评论

题解：AT_tkppc3_d 巨大チェスボード