DP35. 【模板】二维前缀和
描述
给你一个 n 行 m 列的矩阵 A ，下标从1开始。输入描述
第一行包含三个整数n,m,q.输出描述
输出q行，每行表示查询结果。示例1
输入:
3 4 3 1 2 3 4 3 2 1 0 1 5 7 8 1 1 2 2 1 1 3 3 1 2 3 4
输出:
8 25 32
C++ 解法, 执行用时: 54ms, 内存消耗: 9736KB, 提交时间: 2022-01-28
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &f)
{
f=0;T fu=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-'){fu=-1;}c=getchar();}
while(c>='0'&&c<='9') {f=(f<<3)+(f<<1)+(c&15);c=getchar();}
f*=fu;
}
template <typename T>
void print(T x)
{
if(x<0) putchar('-'),x=-x;
if(x<10) putchar(x+48);
else print(x/10),putchar(x%10+48);
}
template <typename T>
void print(T x, char t)
{
print(x);putchar(t);
}
typedef long long ll;
const int maxn=1005;
int n,m,q;
//int a[maxn][maxn];
ll sum[maxn][maxn];
void solve()
{
read(n),read(m),read(q);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
read(sum[i][j]);
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+sum[i][j];
}
}
while(q--)
{
int x1,y1,x2,y2;
read(x1),read(y1),read(x2),read(y2);
ll ans=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
print(ans,'\n');
}
}
int main()
{
// #ifdef AC
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
// #endif
// clock_t program_start_clock=clock();
solve();
// #ifdef NO_TLE
// fprintf(stderr,"\nTotal Time: %lf ms",double(clock()-program_start_clock)/(CLOCKS_PER_SEC/1000));
// #endif
return 0;
}
C++ 解法, 执行用时: 59ms, 内存消耗: 9848KB, 提交时间: 2022-05-08
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T& f) {
f = 0;
T k= 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') {
k = -1;
}
c = getchar();
}
while (c >= '0' && c <= '9') {
f = (f << 3) + (f << 1) + (c & 15);
c = getchar();
}
f *= k;
}
template <typename T>
void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x < 10) putchar(x + 48);
else print(x / 10), putchar(x % 10 + 48);
}
template <typename T>
void print(T x, char t) {
print(x);
putchar(t);
}
typedef long long ll;
const int maxn = 1005;
int n, m, q;
ll sum[maxn][maxn];
void solve() {
read(n), read(m), read(q);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
read(sum[i][j]);
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + sum[i][j];
}
}
while (q--) {
int x1, y1, x2, y2;
read(x1), read(y1), read(x2), read(y2);
ll ans = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
print(ans, '\n');
}
}
int main() {
solve();
return 0;
}
C++ 解法, 执行用时: 64ms, 内存消耗: 13688KB, 提交时间: 2021-12-05
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &f)
{
f=0;T fu=1;char c=getchar();
while(c<'0'||c>'9') {if(c=='-'){fu=-1;}c=getchar();}
while(c>='0'&&c<='9') {f=(f<<3)+(f<<1)+(c&15);c=getchar();}
f*=fu;
}
template <typename T>
void print(T x)
{
if(x<0) putchar('-'),x=-x;
if(x<10) putchar(x+48);
else print(x/10),putchar(x%10+48);
}
template <typename T>
void print(T x, char t)
{
print(x);putchar(t);
}
typedef long long ll;
const int maxn=1005;
int n,m,q;
int a[maxn][maxn];
ll sum[maxn][maxn];
void solve()
{
read(n),read(m),read(q);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
read(a[i][j]);
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
}
while(q--)
{
int x1,y1,x2,y2;
read(x1),read(y1),read(x2),read(y2);
ll ans=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
print(ans,'\n');
}
}
int main()
{
#ifdef AC
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
clock_t program_start_clock=clock();
solve();
#ifdef NO_TLE
fprintf(stderr,"\nTotal Time: %lf ms",double(clock()-program_start_clock)/(CLOCKS_PER_SEC/1000));
#endif
return 0;
}
C++ 解法, 执行用时: 72ms, 内存消耗: 9852KB, 提交时间: 2022-04-12
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x = 0,f = 1;
char ch = getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;
}
const int MAX = 1e3+10;
int n,m,q,t1,t2,t3,t4;
int a[MAX][MAX];
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = read(),m = read(),q = read();
for(int i = 1;i<=n;i++)
for(int j = 1;j<=m;j++) a[i][j]=read()+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
while(q--){
t1 = read(),t2 = read(),t3 = read(),t4 = read();
printf("%lld\n",a[t3][t4]-a[t3][t2-1]-a[t1-1][t4]+a[t1-1][t2-1]);
}
return 0;
}
C++ 解法, 执行用时: 127ms, 内存消耗: 9744KB, 提交时间: 2022-01-08
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e3+5;
ll sum[MAXN][MAXN];
int main()
{
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%lld",&sum[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
while(q--)
{
int x1,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
ll ans=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
printf("%lld\n",ans);
}
}