卿学姐与公主

某日，百无聊赖的卿学姐打开了某11区的某魔幻游戏

在这个魔幻的游戏里，生活着一个美丽的公主，但现在公主被关押在了魔王的城堡中。

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

走过了荒野，翻越了高山，跨过了大洋，卿学姐来到了魔王的第一道城关。

在这个城关面前的是魔王的精锐部队，这些士兵成一字排开。

卿学姐的武器每次只能攻击一个士兵，并造成一定伤害，卿学姐想知道某时刻从L

这个区间内，从开始到现在累计受伤最严重的士兵受到的伤害。

最开始每个士兵的受到的伤害都是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

5 4

2 1 2

1 2 4

1 3 5

2 3 3

0

5

 #include <fstream>

 #include <iostream>

 using namespace std;

 #define MAX 100005

 #define ll long long int

 class SegmentTree

 {

 private:

     int n;

     struct Node

     {

         int left, right, mid;

         ll maxval;

         Node (): maxval()

         {}

     }*tree;

 public:

     SegmentTree (int n): n(n)

     {

         tree = new Node[n<<];

     }

     ~SegmentTree ()

     {

         delete []tree;

     }

     void Build ();

     void Update (int id, int subid, int val);

     ll Search (int id, int left, int right);

 };

 void SegmentTree::Build () //非递归，由于叶子只能出现在树的最后两层，故而可以以tree[i].left < n作为循环条件进行非递归操作。需要说明的是，这里把最后一层的多余内存也初始化了，不过不影响全局。

 {

     int t1;

     tree[].left = ;

     tree[].right = n;

     tree[].mid = (n + ) >> ;

     for (int i = ; tree[i].left < n; i++)

     {

         if (tree[i].left < tree[i].right)

         {

             t1 = i << ;

             tree[t1].left = tree[i].left;

             tree[t1].right = tree[i].mid;

             tree[t1].mid = (tree[t1].left + tree[t1].right) >> ;

             t1++;

             tree[t1].left = tree[i].mid + ;

             tree[t1].right = tree[i].right;

             tree[t1].mid = (tree[t1].left + tree[t1].right) >> ;

         }

     }

 }

 void SegmentTree::Update (int id, int subid, int val)

 {

     if (tree[id].left == tree[id].right)

     {

         tree[id].maxval += val;

     }

     else if (tree[id].mid >= subid)

     {

         Update(id << , subid, val);

         tree[id].maxval = max(tree[id << ].maxval, tree[id].maxval);

     }

     else if (tree[id].mid < subid)

     {

         Update((id << )|, subid, val);

         tree[id].maxval = max(tree[id].maxval, tree[(id << )|].maxval);

     }

 }

 ll SegmentTree::Search (int id, int left, int right)

 {

     if (tree[id].left == left && tree[id].right == right)

     {

         return tree[id].maxval;

     }

     else if (tree[id].mid >= right)

     {

         return Search(id << , left, right);

     }

     else if (tree[id].mid < left)

     {

         return Search((id << )|, left, right);

     }

     else

     {

         return max(Search(id << , left, tree[id].mid), Search((id << )|, tree[id].mid + , right));

     }

 }

 int main ()

 {

     //freopen("D:\\input.in","r",stdin);

     int n, q, t, p, x;

     scanf ("%d %d", &n, &q);

     SegmentTree lv(n);

     lv.Build();

     for (int i = ; i < q; i++)

     {

         scanf ("%d %d %d", &t, &p, &x);

         if (t == )

         {

             lv.Update(, p, x);

         }

         else

         {

             printf("%lld\n", lv.Search(, p, x));

         }

     }

     return ;

 }

 #include <fstream>

 #include <iostream>

 using namespace std;

 #define MAX 100005

 #define ll long long int

 class SegmentTree

 {

 private:

     int n;

     struct Node

     {

         int left, right, mid;

         ll maxval;

         Node (): maxval()

         {}

     }*tree;

 public:

     SegmentTree (int n): n(n)

     {

         tree = new Node[n<<];

     }

     ~SegmentTree ()

     {

         delete []tree;

     }

     void Build (int id, int left, int right);

     void Update (int id, int subid, int val);

     ll Search (int id, int left, int right);

 };

 void SegmentTree::Build (int id, int left, int right) //递归

 {

     tree[id].left = left;

     tree[id].right = right;

     tree[id].mid = (left + right) >> ;

     if (tree[id].mid == right)

     {

         return;

     }

     Build(id << , left, tree[id].mid);

     Build((id << )|, tree[id].mid + , right);

 }

 void SegmentTree::Update (int id, int subid, int val)

 {

     if (tree[id].left == tree[id].right)

     {

         tree[id].maxval += val;

     }

     else if (tree[id].mid >= subid)

     {

         Update(id << , subid, val);

         tree[id].maxval = max(tree[id << ].maxval, tree[id].maxval);

     }

     else if (tree[id].mid < subid)

     {

         Update((id << )|, subid, val);

         tree[id].maxval = max(tree[id].maxval, tree[(id << )|].maxval);

     }

 }

 ll SegmentTree::Search (int id, int left, int right)

 {

     if (tree[id].left == left && tree[id].right == right)

     {

         return tree[id].maxval;

     }

     else if (tree[id].mid >= right)

     {

         return Search(id << , left, right);

     }

     else if (tree[id].mid < left)

     {

         return Search((id << )|, left, right);

     }

     else

     {

         return max(Search(id << , left, tree[id].mid), Search((id << )|, tree[id].mid + , right));

     }

 }

 int main ()

 {

     //freopen("D:\\input.in","r",stdin);

     int n, q, t, p, x;

     scanf ("%d %d", &n, &q);

     SegmentTree lv(n);

     lv.Build(, , n);

     for (int i = ; i < q; i++)

     {

         scanf ("%d %d %d", &t, &p, &x);

         if (t == )

         {

             lv.Update(, p, x);

         }

         else

         {

             printf("%lld\n", lv.Search(, p, x));

         }

     }

     return ;

 }