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

卿学姐与公主

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

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

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

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

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

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

卿学姐的武器每次只能攻击一个士兵，并造成一定伤害，卿学姐想知道某时刻从LL到RR这个区间内，从开始到现在累计受伤最严重的士兵受到的伤害。

最开始每个士兵的受到的伤害都是0

Input

第一行两个整数N,QN,Q表示总共有NN个士兵编号从11到NN，和QQ个操作。

接下来QQ行，每行三个整数，首先输入一个tt，如果tt是11，那么输入p,xp,x，表示卿学姐攻击了pp这个位置的士兵，并造成了xx的伤害。如果tt是22，那么输入L,RL,R，表示卿学姐想知道现在[L,R][L,R]闭区间内，受伤最严重的士兵受到的伤害。

1≤N≤1000001≤N≤100000

1≤Q≤1000001≤Q≤100000

1≤p≤N1≤p≤N

1≤x≤1000001≤x≤100000

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

Output

对于每个询问，回答相应的值

Sample input and output

0

5

Hint

注意可能会爆int哦

思路：

A - 卿学姐与公主

这是专题里少的可怜的水题之一啊！！！

这题是单点更新，区间查询（求最大值）。

用build函数构建线段树，然后update进行单点更新，query查询最大值就好了、、、

节点的附加信息是max，所受伤害的最大值，update就更新的这个

然后自己手写一波就好了（其实我是用的以前写的模板，改了一点东西就好了

　　线段树的相关内容可以去我博客里找找。。

ac代码：

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <queue>

 #include <stack>

 #include <map>

 #include <vector>

 #include <cstdlib>

 #include <string>

 #define PI acos((double)-1)

 #define E exp(double(1))

 using namespace std;

 //#define MOD 772002+233

 #define K 100000

 struct node

 {

     long long maxt,sum;

     long long left,right;

 };

 struct node tree[*K+];

 long long a[*K+];

 int build(int id,int l,int r)

 {

     tree[id].left=l;tree[id].right=r;

     if(l==r)

     {

         tree[id].maxt=tree[id].sum=a[l];

     }

     else

     {

         build(*id,l,(l+r)/);

         build(*id+,(l+r)/+,r);

         tree[id].maxt=max(tree[*id].maxt,tree[*id+].maxt);

         tree[id].sum=(tree[*id].sum+tree[*id+].sum);

     }

     return ;

 }

 int update(int id,int pos,long long v)

 {

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

     {

         tree[id].sum=tree[id].maxt=v+tree[id].sum;

     }

     else

     {

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

         if (pos<=mid) update(id*,pos,v);

             else update(id*+,pos,v);

         tree[id].sum=(tree[id*].sum+tree[id*+].sum);

         tree[id].maxt=max(tree[id*].maxt,tree[id*+].maxt);

     }

     return ;

 }

 long long querySum(int id,int l,int r)

 {

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

             return tree[id].sum;

         else

         {

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

             if (r<=mid) return querySum(id*,l,r);

             else if (l>mid) return querySum(id*+,l,r);

             else return querySum(id*,l,mid)+querySum(id*+,mid+,r);

         }

     }

 long long queryMax(int id,int l,int r)

 {

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

         return tree[id].maxt;

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

     long long ret=;

     if(r<=mid)

         ret=max(ret,queryMax(id<<,l,r));

     else if(l>=mid+)

         ret=max(ret,queryMax((id<<)+,l,r));

     else

     {

         long long a,b;

         a=queryMax(id<<,l,mid);

         b=queryMax((id<<)+,mid+,r);

         return max(a,b);

     }

     return ret;

 }

 int main (void)

 {

     int n,q;

     cin>>n>>q;

     memset(a,,sizeof(a));

     build(,,n);

     while(q--)

     {

         int t;

         scanf("%d",&t);

         if(t==)

         {

             long long x,y;

             scanf("%lld%lld",&x,&y);

             update(,x,y);

         }

         else

         {

             int x,y;

             scanf("%d%d",&x,&y);

             printf("%lld\n",queryMax(,x,y));

         }

     }

     return ;

 }

卿学姐

cdoj1324卿学姐与公主