http://acm.uestc.edu.cn/#/problem/show/1324

卿學姐與公主

Time Limit: 2000/1000MS (Java/Others) ??? Memory Limit: 65535/65535KB (Java/Others)

某日，百無聊賴的卿學姐打開了某11區的某魔幻游戲

在這個魔幻的游戲里，生活著一個美麗的公主，但現在公主被關押在了魔王的城堡中。

英勇的卿學姐拔出利刃沖向了拯救公主的道路。

走過了荒野，翻越了高山，跨過了大洋，卿學姐來到了魔王的第一道城關。

在這個城關面前的是魔王的精銳部隊，這些士兵成一字排開。

卿學姐的武器每次只能攻擊一個士兵，并造成一定傷害，卿學姐想知道某時刻從L

到R

這個區間內，從開始到現在累計受傷最嚴重的士兵受到的傷害。

最開始每個士兵的受到的傷害都是0

Input

第一行兩個整數N,Q表示總共有N個士兵編號從1到N，和Q個操作。

接下來Q行，每行三個整數，首先輸入一個t，如果t是1，那么輸入p,x，表示卿學姐攻擊了p這個位置的士兵，并造成了x的傷害。如果t是2，那么輸入L,R，表示卿學姐想知道現在[L,R]閉區間內，受傷最嚴重的士兵受到的傷害。

1≤N≤100000

1≤Q≤100000

1≤p≤N

1≤x≤100000

1≤L≤R≤N1≤L≤R≤

Output

對于每個詢問，回答相應的值

Sample input and output

Sample InputSample Output

5 4 2 1 2 1 2 4 1 3 5 2 3 3	0 5

?

思路：線段樹 點更新

代碼：

1 #include <fstream> 2 #include <iostream> 3 using namespace std; 4 5 #define MAX 100005 6 #define ll long long int 7 8 class SegmentTree 9 { 10 private: 11 int n; 12 struct Node 13 { 14 int left, right, mid; 15 ll maxval; 16 Node (): maxval(0) 17 {} 18 }*tree; 19 public: 20 SegmentTree (int n): n(n) 21 { 22 tree = new Node[n<<2]; 23 } 24 ~SegmentTree () 25 { 26 delete []tree; 27 } 28 void Build (); 29 void Update (int id, int subid, int val); 30 ll Search (int id, int left, int right); 31 }; 32 void SegmentTree::Build () //非遞歸，由于葉子只能出現在樹的最后兩層，故而可以以tree[i].left < n作為循環條件進行非遞歸操作。需要說明的是，這里把最后一層的多余內存也初始化了，不過不影響全局。 33 { 34 int t1; 35 tree[1].left = 1; 36 tree[1].right = n; 37 tree[1].mid = (n + 1) >> 1; 38 for (int i = 1; tree[i].left < n; i++) 39 { 40 if (tree[i].left < tree[i].right) 41 { 42 t1 = i << 1; 43 tree[t1].left = tree[i].left; 44 tree[t1].right = tree[i].mid; 45 tree[t1].mid = (tree[t1].left + tree[t1].right) >> 1; 46 t1++; 47 tree[t1].left = tree[i].mid + 1; 48 tree[t1].right = tree[i].right; 49 tree[t1].mid = (tree[t1].left + tree[t1].right) >> 1; 50 } 51 } 52 } 53 void SegmentTree::Update (int id, int subid, int val) 54 { 55 if (tree[id].left == tree[id].right) 56 { 57 tree[id].maxval += val; 58 } 59 else if (tree[id].mid >= subid) 60 { 61 Update(id << 1, subid, val); 62 tree[id].maxval = max(tree[id << 1].maxval, tree[id].maxval); 63 } 64 else if (tree[id].mid < subid) 65 { 66 Update((id << 1)|1, subid, val); 67 tree[id].maxval = max(tree[id].maxval, tree[(id << 1)|1].maxval); 68 } 69 } 70 ll SegmentTree::Search (int id, int left, int right) 71 { 72 if (tree[id].left == left && tree[id].right == right) 73 { 74 return tree[id].maxval; 75 } 76 else if (tree[id].mid >= right) 77 { 78 return Search(id << 1, left, right); 79 } 80 else if (tree[id].mid < left) 81 { 82 return Search((id << 1)|1, left, right); 83 } 84 else 85 { 86 return max(Search(id << 1, left, tree[id].mid), Search((id << 1)|1, tree[id].mid + 1, right)); 87 } 88 } 89 90 int main () 91 { 92 //freopen("D:\\input.in","r",stdin); 93 int n, q, t, p, x; 94 scanf ("%d %d", &n, &q); 95 SegmentTree lv(n); 96 lv.Build(); 97 for (int i = 0; i < q; i++) 98 { 99 scanf ("%d %d %d", &t, &p, &x); 100 if (t == 1) 101 { 102 lv.Update(1, p, x); 103 } 104 else 105 { 106 printf("%lld\n", lv.Search(1, p, x)); 107 } 108 } 109 return 0; 110 }

?代碼2：遞歸

1 #include <fstream> 2 #include <iostream> 3 using namespace std; 4 5 #define MAX 100005 6 #define ll long long int 7 8 class SegmentTree 9 { 10 private: 11 int n; 12 struct Node 13 { 14 int left, right, mid; 15 ll maxval; 16 Node (): maxval(0) 17 {} 18 }*tree; 19 public: 20 SegmentTree (int n): n(n) 21 { 22 tree = new Node[n<<2]; 23 } 24 ~SegmentTree () 25 { 26 delete []tree; 27 } 28 void Build (int id, int left, int right); 29 void Update (int id, int subid, int val); 30 ll Search (int id, int left, int right); 31 }; 32 void SegmentTree::Build (int id, int left, int right) //遞歸 33 { 34 tree[id].left = left; 35 tree[id].right = right; 36 tree[id].mid = (left + right) >> 1; 37 if (tree[id].mid == right) 38 { 39 return; 40 } 41 Build(id << 1, left, tree[id].mid); 42 Build((id << 1)|1, tree[id].mid + 1, right); 43 } 44 void SegmentTree::Update (int id, int subid, int val) 45 { 46 if (tree[id].left == tree[id].right) 47 { 48 tree[id].maxval += val; 49 } 50 else if (tree[id].mid >= subid) 51 { 52 Update(id << 1, subid, val); 53 tree[id].maxval = max(tree[id << 1].maxval, tree[id].maxval); 54 } 55 else if (tree[id].mid < subid) 56 { 57 Update((id << 1)|1, subid, val); 58 tree[id].maxval = max(tree[id].maxval, tree[(id << 1)|1].maxval); 59 } 60 } 61 ll SegmentTree::Search (int id, int left, int right) 62 { 63 if (tree[id].left == left && tree[id].right == right) 64 { 65 return tree[id].maxval; 66 } 67 else if (tree[id].mid >= right) 68 { 69 return Search(id << 1, left, right); 70 } 71 else if (tree[id].mid < left) 72 { 73 return Search((id << 1)|1, left, right); 74 } 75 else 76 { 77 return max(Search(id << 1, left, tree[id].mid), Search((id << 1)|1, tree[id].mid + 1, right)); 78 } 79 } 80 81 int main () 82 { 83 //freopen("D:\\input.in","r",stdin); 84 int n, q, t, p, x; 85 scanf ("%d %d", &n, &q); 86 SegmentTree lv(n); 87 lv.Build(1, 1, n); 88 for (int i = 0; i < q; i++) 89 { 90 scanf ("%d %d %d", &t, &p, &x); 91 if (t == 1) 92 { 93 lv.Update(1, p, x); 94 } 95 else 96 { 97 printf("%lld\n", lv.Search(1, p, x)); 98 } 99 } 100 return 0; 101 }

?

總結

以上是生活随笔為你收集整理的CDOJ1324-卿学姐与公主 【线段树点更新】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。