二维数组维护前缀和(pre[i][j] = pre[i][j] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1]),然后根据O(1)的复杂度就能算出范围内所需要的数了,给的数据范围可能没法开数组,但是可以用vector去存,还有就是用一种不太提倡的方法去开,像我的代码一样(官方题解说开一个指针数组,然后new一个...不会)。其他的主要就是一个容斥原理。
#include <bits/stdc++.h> #define ll long long using namespace std; int n,m,d,t; int main() { scanf("%d%d%d",&n,&m,&d); int pre[n + 5][m + 5]; int ans = 0; memset(pre,0,sizeof(pre)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ int x; scanf("%d", &x); if(x >= d)pre[i][j] = 1 + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1]; else pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1]; } } scanf("%d",&t); while(t--){ int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); printf("%d\n", pre[x2][y2] - pre[x2][y1-1] - pre[x1-1][y2] + pre[x1-1][y1-1]); } return 0; }