BZOJ 1452: [JSOI2009]Count – [树状数组/暴力]

题目传送门(BZOJ)
>原文链接<

题解 :

​ PK With Winniechen 的又一道水题。
我们可以按权值分类,暴力建立 100 棵二维树状数组。
由于树状数组维护的是一个前缀和,二维树状数组就只需要查四个前缀和就好啦。
本题考查的是审题~,发现数据范围足够小就能秒切。

代码 :

#include 
int n, m, T, opt;
int t[110][310][310];
int a[310][310];
void fix(int (&t)[310][310], int x, int y, int c) {
    for(int i = x; i <= n; i += i&-i) for(int j = y; j <= m; j += j&-j)
        t[i][j] += c;
}
int inq(int (&t)[310][310], int x, int y) {
    int ret = 0;
    for(int i = x; i; i -= i&-i) for(int j = y; j; j -= j&-j)
        ret += t[i][j];
    return ret;
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= m; j ++ ) {
        scanf("%d", &a[i][j]);
        fix(t[a[i][j]], i, j, 1);
    }
    scanf("%d", &T);
    while(T -- ) {
        scanf("%d", &opt);
        if(opt == 1) {
            int x, y, c;
            scanf("%d%d%d", &x, &y, &c);
            fix(t[a[x][y]], x, y, -1);
            fix(t[a[x][y] = c], x, y, 1);
        } else {
            int x1, x2, y1, y2, c;
            scanf("%d%d%d%d%d", &x1, &x2, &y1, &y2, &c);
            printf("%d\n", inq(t[c], x1-1, y1-1)+inq(t[c], x2, y2)-inq(t[c], x1-1, y2)-inq(t[c], x2, y1-1));
        }
    }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注