1452: [JSOI2009]Count
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 2419 Solved: 1403
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
Sample Output
1
2
2
HINT
裸的二维树状数组。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) > (b) ? (b) : (a))
#define lowbit(a) ((a) & (-(a))) int read()
{
int x = 0;char ch = getchar();char c = ch;
while(ch > '9' || ch < '0')c = ch, ch = getchar();
while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();
if(c == '-')return -x;
return x;
}
const int INF = 0x3f3f3f3f;
const int MAXC = 100 + 10;
const int MAXN = 300 + 10;
const int MAXM = 300 + 10; int n,m;
int data[MAXC][MAXN][MAXM]; int q;
int g[MAXN][MAXM];
int tmp1,tmp2,tmp3,tmp4,tmp5,tmp;
void prin();
int ask(int x,int y,int c)
{
int sum = 0;
for(;x;x -= lowbit(x))
for(int i = y;i;i -= lowbit(i))
sum += data[c][x][i];
return sum;
} int ask(int x1, int y1, int x2, int y2, int c)//左上角,右下角
{
return ask(x2,y2,c) - ask(x2, y1 - 1, c) - ask(x1 - 1, y2, c) + ask(x1 - 1, y1 - 1, c);
} void modify(int x,int y,int c, int num)
{
for(;x <= n;x += lowbit(x))
for(int i = y;i <= m;i += lowbit(i))
data[c][x][i] += num;
}
int main()
{
n = read();m = read();
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= m;j ++)
{
tmp = read();
modify(i, j, tmp, 1);
g[i][j] = tmp;
}
}
q = read();
for(int i = 1;i <= q;i ++)
{
tmp = read();
if(tmp == 1)
{
tmp1 = read();tmp2 = read();tmp3 = read();
modify(tmp1, tmp2, g[tmp1][tmp2], -1);
modify(tmp1, tmp2, tmp3, 1);
g[tmp1][tmp2] = tmp3;
}
if(tmp == 2)
{
tmp1 = read();tmp2 = read();tmp3 = read();tmp4 = read();tmp5 = read();
printf("%d\n", ask(tmp1,tmp3,tmp2,tmp4,tmp5));
}
}
return 0;
}