contents
Problem
有一長度為 n 的都市地帶,每一次將會做區段的都市更新,將建築物都增加高度 v。
操作
- B X Y V : 將區間
[X, Y]
都增加 V 高度
- Q X : 詢問當前位置 X 的建築物高度為何
(題目中的圖示貌似有錯誤)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
|
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
|
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)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
|
#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("%dn", 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 */
|
近期评论