D - Counting Black POJ - 1656 (不用树状数组的情况

 前几题运用了树状数组的 单点修改+区间查询,一维区间修改+单点查询(差分法),二维区间修改+单点查询(差分法)

这些都是树状数组的常规操作

树状数组还可以通过维护两个数组实现一维的区间修改+区间查询,详见:https://www.cnblogs.com/lcf-2000/p/5866170.html

但是二维的区间修改+区间查询很不好实现,这时不如直接用线段树实现

题目:

有一块有100*100个的格子的板子如下图。左上角的格子是(1,1),右下角的格子是(100,100)

我们可以对这个板子有三种不同的命令:


1.    WHITE  x, y, L     // 在板子上画一个白方块, 

                           //)方块的左上角是(x,y)

                           // 右下角是 (x+L-1, y+L-1)



2.    BLACK  x, y, L     // 在板子上画一个黑方块

                           // 方块的左上角是 (x, y)

                           // 右下角是 (x+L-1, y+L-1)



3.    TEST     x, y, L    // 询问方块(x,y)到(x+L-1,y+L-1)中黑色方块的数量 


开始的时候,板子上的方块都是白色的。 我们对板子进行一系列的操作。你的任务就是写一个程序,计算出指定区域的黑块的数量。 

 

注意题目描述虽然是线段树或树状数组的套路,但数据范围较小(100*100),操作简单

这时侯就没必要用树状数组 ,看其他答案的树状数组区间修改依旧是逐点遍历实现的 ,这时候倒不如直接暴力

树状数组 修改O(nlog n) 查询O(log n)

暴力 修改 O(n)查询(n)

#include <cstdio>
#include <cstring>

using namespace std;
// 这题数据很小,完全没必要用树状数组
// 而且二维树状数组区间修改+区间查询的操作 我也不会

int pic[105][105];

int main( ){
     int n;
     char op[10];
     int ans;
     int x,y,l;
     scanf("%d" ,&n);
     while( n--){
        scanf("%s",op);
        if( op[0]=='B'){

            scanf("%d%d%d" ,&x ,&y ,&l);
            for( int i=x ; i<x+l ;i++)
            for( int j=y ; j<y+l ;j++){
                if( pic[i][j] == 0)pic[i][j]++;
            }
        }
        if( op[0]=='W'){
            scanf("%d%d%d" ,&x ,&y ,&l);
            for( int i=x ; i<x+l ;i++)
            for( int j=y ; j<y+l ;j++){
                if( pic[i][j] == 1)pic[i][j]--;
            }
        }
        if( op[0]=='T'){
            ans=0;
            scanf("%d%d%d" ,&x ,&y ,&l);
             for( int i=x ; i<x+l ;i++)
            for( int j=y ; j<y+l ;j++){
                ans+=pic[i][j];
            }
            printf("%d\n" ,ans);
        }
     }
     return 0;
}

 

上一篇:RMAN跨小版本跨平台与字节序传输表空间


下一篇:1004 Counting Leaves 对于树的存储方式的回顾