首页 > 其他 > 详细

poj - 1195 - Mobile phones(树状数组)

时间:2014-01-22 22:49:50      阅读:387      评论:0      收藏:0      [点我收藏+]

题意:给出一个S * S的矩阵,每个位置可以放手机,初始时每个位置的都是空的。现要执行一些操作:1 X Y A,在位置(X, Y)增加A台手机,2 L B R T,查询(L, B)到(R, T)的矩阵的手机有多少(0 <= X, Y < S, 1 <= S <= 1024, -32768 <= A <= 32767, 手机总和最多只有2^30台)。

题目链接:http://poj.org/problem?id=1195

——>>二维树状数组模板题。。。设c[x][y]表示[x - lowerbit(x) + 1, x], [y - lowerbit(y) + 1, y]的所有点的手机总台数。于是……#^_^

#include <cstdio>
#include <cstring>

using namespace std;

const int maxs = 1024 + 10;

int S;
int c[maxs][maxs];

int lowerbit(int x) {
    return x & (-x);
}

void add(int x, int y, int v) {
    for(int i = x; i <= S; i += lowerbit(i))
        for(int j = y; j <= S; j += lowerbit(j))
            c[i][j] += v;
}

int sum(int x, int y) {
    int ret = 0;
    for(int i = x; i > 0; i -= lowerbit(i))
        for(int j = y; j > 0; j -= lowerbit(j))
            ret += c[i][j];
    return ret;
}

int main()
{
    int instraction, X, Y, A, L, B, R, T;
    while(scanf("%d", &instraction) == 1) {
        switch(instraction) {
        case 0: {
            scanf("%d", &S);
            S++;
            memset(c, 0, sizeof(c));
            break;
        }
        case 1: {
            scanf("%d%d%d", &X, &Y, &A);
            add(X+1, Y+1, A);
            break;
        }
        case 2: {
            scanf("%d%d%d%d", &L, &B, &R, &T);
            L++;
            B++;
            R++;
            T++;
            printf("%d\n", sum(R, T) - sum(R, B-1) - sum(L-1, T) + sum(L-1, B-1));
            break;
        }
        default: break;
        }
    }
    return 0;
}



poj - 1195 - Mobile phones(树状数组)

原文:http://blog.csdn.net/scnu_jiechao/article/details/18658633

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!