题意
题目链接 https://www.luogu.org/problemnew/show/P4054
Sol
很傻 x 的题..
c 才 100, n, m 才 300, 直接开 100 个二维树状数组就做完了..
- #include<bits/stdc++.h>
- using namespace std;
- const int MAXN = 301;
- inline int read() {
- char c = getchar(); int x = 0, f = 1;
- while(c <'0' || c> '9') {if(c == '-') f = -1; c = getchar();}
- while(c>= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
- return x * f;
- }
- int N, M, col[MAXN][MAXN];
- struct BIT {
- #define lb(x) (x & (-x))
- int T[MAXN][MAXN];
- void Add(int x, int y, int v) {
- for(int i = x; i <= N; i += lb(i))
- for(int j = y; j <= M; j += lb(j))
- T[i][j] += v;
- }
- int sum(int x, int y) {
- int ans = 0;
- for(int i = x; i; i -= lb(i))
- for(int j = y; j; j -= lb(j))
- ans += T[i][j];
- return ans;
- }
- int Query(int x1, int x2, int y1, int y2) {
- return sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1);
- }
- }T[101];
- int main() {
- N = read(); M = read();
- for(int i = 1; i <= N; i++)
- for(int j = 1; j <= M; j++)
- T[col[i][j] = read()].Add(i, j, 1);
- int Q = read();
- while(Q--) {
- int opt = read(), a = read(), b = read(), c = read(), d, e;
- if(opt == 1) T[col[a][b]].Add(a, b, -1), T[col[a][b] = c].Add(a, b, 1);
- if(opt == 2) d = read(), e = read(), printf("%d\n", T[e].Query(a, b, c, d));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2945335.html