DP38. 【模板】二维差分
描述
给你一个n行m列的矩阵，下标从1开始。输入描述
第一行包含三个整数n,m,q.输出描述
输出n行，每行m个数，每个数用空格分开，表示这个矩阵。示例1
输入:
2 3 4 1 2 3 4 5 6 1 1 2 2 3 1 2 2 3 -1 1 1 1 3 4 1 1 2 1 1
输出:
9 8 6 8 7 5
C++ 解法, 执行用时: 65ms, 内存消耗: 18300KB, 提交时间: 2021-12-06
#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;
int n,m,q;
ll a[1005][1005];
ll b[1005][1005];
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]);
}
while(q--)
{
ll x1,y1,x2,y2,k;
read(x1),read(y1),read(x2),read(y2),read(k);
b[x1][y1]+=k;
b[x2+1][y2+1]+=k;
b[x2+1][y1]-=k;
b[x1][y2+1]-=k;
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
print(a[i][j]+b[i][j],' ');
}
printf("\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++ 解法, 执行用时: 65ms, 内存消耗: 18452KB, 提交时间: 2022-05-08
#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;
}
void write(int x) {
if (x < 0)putchar('-'), x = -x;
if (x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
const int MAX = 1e3 + 10;
int n, m, q, t1, t2, t3, t4, k;
int a[MAX][MAX], s[MAX][MAX];
signed main() {
n = read(), m = read(), q = read();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)a[i][j] = read();
while (q--) {
t1 = read(), t2 = read(), t3 = read(), t4 = read(), k = read();
s[t1][t2] += k, s[t3 + 1][t4 + 1] += k, s[t1][t4 + 1] -= k, s[t3 + 1][t2] -= k;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1],
write(s[i][j] + a[i][j]), putchar(' ');
putchar('\n');
}
return 0;
}
C++ 解法, 执行用时: 73ms, 内存消耗: 12748KB, 提交时间: 2022-07-19
//#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define FR(a, b, c) for (int a = (b), LEN = (c); a <= LEN; ++a)
#define FD(a, b, c) for (int a = (b), LEN = (c); a >= LEN; --a)
#define endl "\n"
typedef long long ll;
inline int in() {
int f = 0;
int 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();
return f *= fu;
}
const int N=1e3+5;
ll b[N][N];
inline void IN(int x1,int y1,int x2,int y2,ll c){b[x1][y1]+=c,b[x2+1][y1]-=c,b[x1][y2+1]-=c,b[x2+1][y2+1]+=c;}
void solve() {
int n, m, q;
n=in(),m=in(),q=in();
FR(i,1,n){ FR(j,1,m){ int x; x=in(); IN(i,j,i,j,x); } }
while(q--) IN(in(),in(),in(),in(),in());
FR(i,1,n){
FR(j,1,m)printf("%lld ",b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]);
puts("");
}
}
signed main() {
int _ = 1; // cin>>_;
while (_--) solve();
return 0;
}
C++ 解法, 执行用时: 78ms, 内存消耗: 18344KB, 提交时间: 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;
}
void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>=10) write(x/10);
putchar(x%10+'0');
}
const int MAX = 1e3+10;
int n,m,q,t1,t2,t3,t4,k;
int a[MAX][MAX],s[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();
while(q--){
t1=read(),t2=read(),t3=read(),t4=read(),k=read();
s[t1][t2]+=k,s[t3+1][t4+1]+=k,s[t1][t4+1]-=k,s[t3+1][t2]-=k;
}
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++)
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1],write(s[i][j]+a[i][j]),putchar(' ');
putchar('\n');
}
return 0;
}
C++ 解法, 执行用时: 98ms, 内存消耗: 18296KB, 提交时间: 2022-01-25
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e3+5;
ll a[MAXN][MAXN],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",&a[i][j]);
while(q--)
{
int x1,x2,y1,y2,k;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k);
sum[x1][y1]+=k;
sum[x2+1][y2+1]+=k;
sum[x2+1][y1]-=k;
sum[x1][y2+1]-=k;
}
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]+=sum[i][j];
}
for(int i=1;i<=n;i++,puts(""))
for(int j=1;j<=m;j++)
printf("%lld ",a[i][j]);
}