CF1722E Counting Rectangles

2022-09-02

字数统计: 558 | 阅读时长≈ 2 分钟

题意

有 $T$ 组数据，每组数据给出 $n$ 个矩形以及它们的长宽 $h_i,w_i$ 。有 $q$ 次询问，每次询问输入四个数 $h_s,w_s,h_b,w_b$ （这些数和刚刚输入的矩形无关），输出满足的矩形面积之和。

数据范围： $1\leq T\leq 100,1\leq n,q\leq 10^5,1\leq h_i,w_i \leq 1000,1\leq h_s<h_b,w_s<w_b \leq 1000$

思路

对于询问，我们肯定不能暴力枚举每个矩形，否则时间复杂度 $O(qn)$ 会超时。从另一个角度看，给出的坐标范围为 $[1,1000]$ ，我们可以用一个二位数组来存储每一个矩形，下标代表坐标，值为面积。怎么才能快速算出满足 $h_i \in (h_s,h_w),w_i\in (w_s,w_w)$ 矩形总面积呢？

通过二维前缀和或二维树状数组来解决本题。

代码

题解都是前缀和，于是我写了份二维树状数组的

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int M=1e3+9;
int T,n,q;
ll tr[M][M];

int lowbit(int x){
    return x&-x;
}
void add(int x,int y,ll d){//在(x,y)处加上矩形的面积
    for(int i=x;i<=1e3;i+=lowbit(i)){
        for(int j=y;j<=1e3;j+=lowbit(j)) tr[i][j]+=d;
    }
}
ll sum(int x,int y){//求前缀和
    ll ans=0;
    for(int i=x;i;i-=lowbit(i)){
        for(int j=y;j;j-=lowbit(j)) ans+=tr[i][j];
    }
    return ans;
}

int main(){
    scanf("%d",&T);
    while(T--){
        memset(tr,0,sizeof(tr));//记得清空树状数组
        scanf("%d%d",&n,&q);
       ll x,y;
        for(int i=1;i<=n;i++){
            scanf("%lld%lld",&x,&y);
            add(x,y,x*y);
        }
        int c,d,e,f;
        while(q--){
            scanf("%d%d%d%d",&c,&d,&e,&f);
            printf("%lld\n",sum(e-1,f-1)-sum(c,f-1)-sum(e-1,d)+sum(c,d));//求出区间内的矩形面积总和
        }
    }
    return 0;
}

打赏

版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！