本系列是模版系列,会整理
关于思路大家可参照题目信息的链接地址或者相关书籍,文章旨在分享代码。
这是一道模板题。
给出一个
的零矩阵 A,你需要完成如下操作:
1 x y k
:表示元素 A_{x,y} 自增 k;2 a b c d
:表示询问左上角为 (a,b),右下角为 (c,d) 的子矩阵内所有数的和。输入的第一行有两个正整数 n, m; 接下来若干行,每行一个操作,直到文件结束。
对于每个 2
操作,输出一个整数,表示对于这个操作的回答。
输入复制
2 2
1 1 1 3
1 2 2 4
2 1 1 2 2
输出复制
7
,保证操作数目不超过
,且询问的子矩阵存在。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
#define endl '\n';
typedef long long LL;
struct node {
LL w, d;
};
struct FenwickTree {
vector<vector<LL>> c;
int n, m;
FenwickTree(int l, int m) :
n(l), c(l + 1, vector<LL>(m + 1)), m(m) {}
int lowbit(int a) {
return (-a) & a;
}
LL cnt(int x, int y) {
LL ans = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
for (int j = y; j > 0; j -= lowbit(j)) {
ans += c[i][j];
}
}
return ans;
}
void add(int x, int y, LL w) {
for (int i = x; i <= n; i += lowbit(i)) {
for (int j = y; j <= m; j += lowbit(j)) {
c[i][j] += w;
}
}
}
LL ask(int x1, int y1, int x2, int y2) {
return cnt(x2, y2) - cnt(x2, y1 - 1) - cnt(x1 - 1, y2) + cnt(x1 - 1, y1 - 1);
}
};
void best_coder() {
int n, m;
scanf("%d%d", &n, &m);
FenwickTree ft(n, m);
int a;
while(~scanf("%d", &a)) {
if (a == 1) {
int l, r;
LL w;
scanf("%d%d%lld", &l, &r, &w);
ft.add(l, r, w);
} else {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%lld\n", ft.ask(x1, y1, x2, y2));
}
}
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// freopen("xxx.in", "r", stdin);
// freopen("xxx.out", "w", stdout);
// 小码匠
best_coder();
// 最优解
// happy_coder();
// fclose(stdin);
// fclose(stdout);
return 0;
}