POJ3467（预处理）

Cross Counting

Time Limit: 1000MS		Memory Limit: 131072K
Total Submissions: 1331		Accepted: 375

Description

Given a N × M grid with different colors on each cell, your task is to calculate the total amount of crosses of a specific color. We say there exists a cross of size k centered at the cell (x,y) iff all cells lying in the x-th row or the y-th column and within a distance of k from (x,y) share the same color. Note that if two crosses have the same center but different sizes we consider they are distinct. Unfortunately, the color of each cell may varies by time and you have to respond to all the queries.

Input

There are four integers, N, M, C, Q, in the first line. (1 ≤ N, M, C ≤ 100, 1 ≤ Q ≤ 10000)
The next N lines each contains M integers between 1 and C which describe the color of cells.
The following Q lines each has either the form "C i j k" indicating to change the color of cell (i, j) into k, or the form "Q c" indicating to query the total amount of crosses of color c. (1 ≤ i ≤ N, 1 ≤ j ≤ M, 1 ≤ k, c ≤ C)

Output

Output the answer to each query.

Sample Input

Sample Output

Source

POJ Monthly--2007.11.25, Yang Yi

题目看起来有线段树的味道，我线段树能力有限。

发现N,M都非常少，用O(N*M*(N+M))做预处理。

对于每次更新。改变的是十字架。所以更新须要O(N+M)个更新。

我在外层加了一层哨兵。写起来比較顺畅。

/***********************************************************
	> OS     : Linux 3.13.0-24-generic (Mint-17)
	> Author : yaolong
	> Mail   : dengyaolong@yeah.net
	> Time   : 2014年10月15日 星期三 07时11分26秒
 **********************************************************/
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
const int N = 205;
int mp[N][N];
int cnt[N][N];
int color[N];
void update ( int i, int j )
{
    cnt[i][j] = 0;
    for ( int k = 1;; k++ )
    {
        if ( mp[i + k][j] == mp[i][j] && mp[i - k][j] == mp[i][j] && mp[i][j + k] == mp[i][j] && mp[i][j - k] == mp[i][j] )
        {
            cnt[i][j]++;
        }
        else
        {
            return ;
        }
    }
}
int main()
{
    int n, m, c, q;
    while ( scanf ( "%d%d%d%d", &n, &m, &c, &q ) != EOF )
    {
        int i, j, k;
        memset ( color, 0, sizeof ( color ) );
        memset ( mp, 63, sizeof ( mp ) );
        memset ( cnt, 0, sizeof ( cnt ) );
        for ( i = 1; i <= n; i++ )
        {
            for ( j = 1; j <= m; j++ )
            {
                scanf ( "%d", &mp[i][j] );
            }
        }
        for ( i = 1; i <= n; i++ )
        {
            for ( j = 1; j <= m; j++ )
            {
                update ( i, j );
                color[mp[i][j]] += cnt[i][j];
            }
        }
        char tmp;
        while ( q-- )
        {
            scanf ( " %c", &tmp );
            if ( tmp == 'Q' )
            {
                scanf ( "%d", &i );
                printf ( "%d
", color[i] );
            }
            else
            {
                scanf ( "%d%d%d", &i, &j, &k );
                if ( mp[i][j] == k )
                {
                    continue;
                }
                color[mp[i][j]] -= cnt[i][j];
                mp[i][j] = k;
                update ( i, j );
                color[mp[i][j]] += cnt[i][j];
                //cout<<cnt[i][j]<<" "<<i<<j<<endl;
                for ( int ak = 1; ak <= n; ak++ )
                {
                    if ( i != ak )
                    {
                        color[mp[ak][j]] -= cnt[ak][j]; //减掉
                        update ( ak, j );
                        color[mp[ak][j]] += cnt[ak][j];
                    }
                }
                for ( int ak = 1; ak <= m; ak++ )
                {
                    if ( j != ak )
                    {
                        color[mp[i][ak]] -= cnt[i][ak]; //减掉
                        update ( i, ak );
                        color[mp[i][ak]] += cnt[i][ak];
                    }
                }
            }
        }
    }
    return 0;
}