首页 > 代码库 > POJ 2155 Matrix (树状数组 && 区间计数)

POJ 2155 Matrix (树状数组 && 区间计数)

2024-09-27 21:43:02   217人阅读

题意 : 给出一个N*N的矩阵, 矩阵只有可能包含0或1, 一开始则全部是0。对于矩阵可以进行两种操作, 第一种是输入 C x1 y1 x2 y2 表示, 对以(x1, y1)为左上角, 以(x2, y2)为右下角构成的矩形区域内的数全部进行取反操作, 即0变1、1变0。第二种是Q X Y, 表示查询现在这个矩阵的(X, Y)点到底是0还是1。总共有T次操作, 对于C操作进行相应的修改, 对于Q操作要对应输出！

 

分析 : 据说是楼教主出的题, 自己确实想不出什么高效的办法, 参考网上的题解, 才得知解题思想源自一篇国家队论文, 说简单一点就是对于题目要求的C操作, 实际上只要更新这个小矩形区域的四个点即可, 也就是不必全部照样更新。在Q操作查询时候也只要进行二维的树状数组进行(1,1)到(X, Y)点的矩形区域求和, 然后将求和结果%2, 如果得1即这个点被进行了奇数次操作, 所以应为1, 得0则反之。至于为什么或者如何做, 论文比讲的很清楚, 请百度: 《浅谈信息学竞赛中的“0”和“1”》

 

瞎想:很值得借鉴的是对于是否是0或1的判断, 被转化成判断了对这个点操作次数的奇偶。还有对于区间的修改, 对于一维只进行两点的起始标记, 二维则进行四个点的起始标记, 这个也是厉害！

 

技术分享 
#include<stdio.h>
#include<string.h>
#define lowbit(i) (i&(-i))
const int maxn = 1001;
int c[maxn][maxn], n;
inline void add(int row, int col)
{
    for(int i=row; i<=n; i+=lowbit(i)){
        for(int j=col; j<=n; j+=lowbit(j)){
            c[i][j]++;
        }
    }
}
int sum(int row, int col)
{
    int ans = 0;
    for(int i=row; i>0; i-=lowbit(i)){
        for(int j=col; j>0; j-=lowbit(j)){
            ans += c[i][j];
        }
    }
    return ans;
}
inline void initialize(int k)
{
    for(int i=0; i<=k; i++){
        memset(c[i], 0, sizeof(c[i]));
    }
}
int main(void)
{
    int nCase;
    scanf("%d", &nCase);
    while(nCase--){
        scanf("%d", &n);
        initialize(n);
        int num;
        scanf("%d", &num);
        while(num--){
            char command;
            scanf(" %c", &command);
            if(command==‘C‘){
                int x1, y1, x2, y2;
                scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
                add(x1, y1);
                add(x2+1, y1);
                add(x1, y2+1);
                add(x2+1, y2+1);
            }else{
                int x, y;
                scanf("%d%d", &x, &y);
                int SUM = sum(x, y);
                printf("%d\n", SUM&1);//&1和%2好像效率一样！
            }
        }
        puts("");//注意这里, 用例之间要空个行, 避免PE
    }
    return 0;
}
View Code

 

POJ 2155 Matrix (树状数组 && 区间计数)


联系
我们