毒瘤输入,卡死我了
输入是x1 x2 y1 y2 c
正常人的输入都是x1 y1 x2 y2 c
这题不至于困难难度,各个颜色之间互不影响。而且矩阵值域很小,也不需要离散化,套路题
给每个颜色开一个二维树状数组就可以了,$1\le c\le 100$,最多 $100$ 个
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../template/debug.h"
#else
#define debug(...) 42
#endif
template <typename T> class fenwick {
public:
vector<vector<T>> fenw;
int n, m;
fenwick(int _n, int _m) : n(_n), m(_m) {
fenw.resize(n + 1);
for (int i = 0; i < n; ++i) {
fenw[i].resize(m);
}
}
inline void modify(int x, int y, T v) {
assert(x >= 0 && x < n);
assert(y >= 0 && y < m);
for (int i = x; i < n; i |= (i + 1)) {
for (int j = y; j < m; j |= (j + 1)) {
fenw[i][j] += v;
}
}
}
inline T get(int x, int y) {
assert(x >= 0 && x < n);
assert(y >= 0 && y < m);
T res{};
for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
for (int j = y; j >= 0; j = (j & (j + 1)) - 1) {
res += fenw[i][j];
}
}
return res;
}
inline T get(int x1, int y1, int x2, int y2) {
assert(x1 <= x2 && y1 <= y2);
assert(x1 >= 0 && x1 < n && x2 >= 0 && x2 < n);
assert(y1 >= 0 && y1 < m && y2 >= 0 && y2 < m);
T res = get(x2, y2);
if (x1 - 1 >= 0) {
res -= get(x1 - 1, y2);
}
if (y1 - 1 >= 0) {
res -= get(x2, y1 - 1);
}
if (x1 - 1 >= 0 && y1 - 1 >= 0) {
res += get(x1 - 1, y1 - 1);
}
return res;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m, 0));
vector<fenwick<int>> fenw(100, fenwick<int>(n, m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
a[i][j]--;
fenw[a[i][j]].modify(i, j, 1);
}
}
int q;
cin >> q;
while (q--) {
int opt;
cin >> opt;
if (opt == 1) {
int x, y, c;
cin >> x >> y >> c;
--x, --y, --c;
fenw[a[x][y]].modify(x, y, -1);
a[x][y] = c;
fenw[c].modify(x, y, 1);
} else {
int xa, xb, ya, yb, c;
cin >> xa >> xb >> ya >> yb >> c; // 坑死我了
--xa, --xb, --ya, --yb, --c;
cout << fenw[c].get(xa, ya, xb, yb) << '\n';
}
}
return 0;
}
%%%