UVa 12769 - Kool Konstructions

1. Problem
2. Sample Input
3. Sample Output
4. Solution

Problem

有一長度為 n 的都市地帶，每一次將會做區段的都市更新，將建築物都增加高度 v。

操作

B X Y V ：將區間 [X, Y] 都增加 V 高度
Q X ：詢問當前位置 X 的建築物高度為何

(題目中的圖示貌似有錯誤)

Sample Input

Sample Output

Solution

想要區間更新、單點查詢，有兩種方案 segment tree 附加懶操作、或者 binary indexed tree、最後是塊狀鏈表這幾種方式。這裡使用 binary indexed tree。雖然 binary indexed tree 原本的操作是單點修改，前綴總和查找。利用這一點完成區間修改的操作。

由於這一題還是單純的加法，那麼符合加法原則，當區間修改 B X Y V 時，相當於修改單點 Arr[X] += V，Arr[Y+1] -= V，從前綴和 SUM[1...Z] = \sum Arr[i]來看，保證只有區間 [X, Y] 的詢問增加了 V 值，其他保持不變。

單筆操作都是 O(log n)

#include <stdio.h> 
#include <string.h> 
#define MAXN 100000
int BIT[MAXN + 5];
void modify(int x, int val, int L) {
    while (x <= L) {
        BIT[x] += val;
        x += x&(-x);
    }
}
int query(int x) {
    int ret = 0;
    while (x) {
        ret += BIT[x];
        x -= x&(-x);
    }
    return ret;
}
int main() {
    int n, a, b, y;
    char cmd[8];
    while (scanf("%d", &n) == 1 && n) {
        memset(BIT, 0, sizeof(BIT));
        for (int i = 0; i < n; i++) {
            scanf("%s", cmd);
            if (cmd[0] == 'B') {
                scanf("%d %d %d", &a, &b, &y);
                modify(a, y, MAXN);
                modify(b + 1, -y, MAXN);
            } else {
                scanf("%d", &a);
                int ret = query(a);
                printf("%d\n", ret);
            }
        }
    }
    return 0;
}
/*
9
B 5 5 2
B 8 8 2
B 10 13 1
Q 8
B 8 13 1
Q 8
B 15 16 1
B 2 10 1
Q 8
9
B 5 5 2
B 8 8 2
B 10 13 1
Q 8
B 8 13 1
Q 8
B 15 16 1
B 2 10 1
Q 8
0
*/

Morris' Blog

UVa 12769 - Kool Konstructions

contents

Problem

Sample Input

Sample Output

Solution