P4054 计数问题

问题

P4054 [JSOI2009] 计数问题
维护一个带颜色的方格，支持修改单个格子的颜色，以及询问一个子矩形中指定颜色出现了多少次。

数据规模：$n,m\le 300$，操作数不超过 $2\times 10^5$，颜色不超过 $100$ 种。

这其实是带单点修改的二维矩形计数。由于查询还指定颜色，可以为每种颜色分别维护一棵二维树状数组；换色时在旧颜色中减一、在新颜色中加一，矩形询问再用四个前缀容斥。

▶

P4054

// 二维树状数组：单点修改，矩形查询
struct BIT2D {
/* ================================================== */
ll tr[maxn][maxm];
int n, m;
void init( int N, int M ) {
    n = N, m = M;
    for( int i = 0; i <= n; ++ i ) fill( tr[i], tr[i] + m + 1, 0 );
}
// 单点修改 a[x][y] += val
void add( int x, int y, ll val ) {
    for( int i = x; i <= n; i += i & -i )
        for( int j = y; j <= m; j += j & -j )
            tr[i][j] += val;
}
// 查询前缀矩形 [1, x] × [1, y]
ll ask( int x, int y ) {
    ll res = 0;
    for( int i = x; i; i -= i & -i )
        for( int j = y; j; j -= j & -j )
            res += tr[i][j];
    return res;
}
// 查询矩形 [x1, x2] × [y1, y2]
ll ask( int x1, int y1, int x2, int y2 ) {
    return ask( x2, y2 )
         - ask( x1 - 1, y2 )
         - ask( x2, y1 - 1 )
         + ask( x1 - 1, y1 - 1 );
}
/* ================================================== */
} bit[101];

int col[maxn][maxm];

void solve( ) {
    int n = read( ), m = read( );

    for( int c = 1; c <= 100; ++ c ) {
        bit[c].init( n, m );
    }

    for( int i = 1; i <= n; ++ i ) {
        for( int j = 1; j <= m; ++ j ) {
            col[i][j] = read( );
            bit[col[i][j]].add( i, j, 1 );
        }
    }

    int q = read( );
    for( int i = 1; i <= q; ++ i ) {
        int opt = read( );

        if( opt == 1 ) {
            int x = read( ), y = read( );
            int c = read( );
            int color = col[x][y];
            bit[color].add( x, y, -1 );
            bit[c].add( x, y, 1 );
            col[x][y] = c;
        }
        else {
            int x1 = read( ), x2 = read( );
            int y1 = read( ), y2 = read( );
            int c = read( );
            ll ans = bit[c].ask( x1, y1, x2, y2 );
            cout << ans << '\n';
        }
    }
}

记录

• 归属：二维树状数组。
• 新增：按小颜色值域拆分数据结构，动态维护指定类别的矩形计数。
• 分类：待定。