CF1722E

分别给定 $n$ 个正整数 $h_i,w_i$ ，有 $q$ 次询问。

对于每次询问，输入四个整数 $h_s,w_s,h_b,w_b$，输出满足 $h_i \in (h_s,h_b)$ ,$w_i\in(w_s,w_b)$ 的 $\sum h_i \cdot w_i$

思路

把一个长 $h$ 宽 $w$ 的长方形看成在位置 $(h,w)$ 上加 $h*w$ 。

那么对于每次询问，求的就是 $(h_s+1,w_s+1)$ 为左上角， $(h_b-1,w_b-1)$ 为右下角的长方形内的值之和。

于是直接二维前缀和即可。

赛时没有想到这种转化，而且二维前缀和也忘光了…..今天复习复习才会写。

代码

#include<bits/stdc++.h>
#define ll long long 
#define N 1010

using namespace std;

inline ll read() {
    ll w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int T;
int n,q;
ll a[N][N],s[N][N];

void init() {
    memset(a,0,sizeof(a));
    memset(s,0,sizeof(s));
}

int main() {
    T=read();
    while(T--) {
        n=read(),q=read();
        init();
        for(int i=1;i<=n;i++) {
            ll h=read(),w=read();
            a[h][w]+=h*w;
        }
        
        for(int i=1;i<=1000;i++) {
            for(int j=1;j<=1000;j++) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
        }
        for(int i=1;i<=q;i++) {
            ll hs=read()+1,ws=read()+1,hb=read()-1,wb=read()-1;
            ll ans=s[hb][wb]-s[hb][ws-1]-s[hs-1][wb]+s[hs-1][ws-1];
            printf("%lld\n",ans);
        }
    }    
    system("pause");
    return 0;
}