卿学姐与公主

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

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

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

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

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

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

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

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

Input

第一行两个整数

接下来

Output

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

Sample input and output

Sample Input	Sample Output
5 4 2 1 2 1 2 4 1 3 5 2 3 3	0 5

Hint

注意可能会爆int哦

思路：

A - 卿学姐与公主

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

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

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

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

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

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

ac代码：

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <cstdio>
  4 #include <cmath>
  5 #include <cstring>
  6 #include <queue>
  7 #include <stack>
  8 #include <map>
  9 #include <vector>
 10 #include <cstdlib>
 11 #include <string>
 12 
 13 #define PI acos((double)-1)
 14 #define E exp(double(1))
 15 using namespace std;
 16 //#define MOD 772002+233
 17 #define K 100000
 18 struct node
 19 {
 20     long long maxt,sum;
 21     long long left,right;
 22 };
 23 struct node tree[4*K+4];
 24 long long a[3*K+4];
 25 int build(int id,int l,int r)
 26 {
 27     tree[id].left=l;tree[id].right=r;
 28     if(l==r)
 29     {
 30         tree[id].maxt=tree[id].sum=a[l];
 31     }
 32     else
 33     {
 34         build(2*id,l,(l+r)/2);
 35         build(2*id+1,(l+r)/2+1,r);
 36         tree[id].maxt=max(tree[2*id].maxt,tree[2*id+1].maxt);
 37         tree[id].sum=(tree[2*id].sum+tree[2*id+1].sum);
 38     }
 39     return 0;
 40 }
 41 
 42 int update(int id,int pos,long long v)
 43 {
 44     if(tree[id].left == tree[id].right)
 45     {
 46         tree[id].sum=tree[id].maxt=v+tree[id].sum;
 47     }
 48     else
 49     {
 50         int mid=(tree[id].left+tree[id].right)/2;
 51         if (pos<=mid) update(id*2,pos,v);
 52             else update(id*2+1,pos,v);
 53         tree[id].sum=(tree[id*2].sum+tree[id*2+1].sum);
 54         tree[id].maxt=max(tree[id*2].maxt,tree[id*2+1].maxt);
 55     }
 56     return 0;
 57 }
 58 
 59 long long querySum(int id,int l,int r)
 60 {
 61         if (tree[id].left==l&&tree[id].right==r)
 62             return tree[id].sum;
 63         else
 64         {
 65             int mid=(tree[id].left+tree[id].right)/2;
 66             if (r<=mid) return querySum(id*2,l,r);
 67             else if (l>mid) return querySum(id*2+1,l,r);
 68             else return querySum(id*2,l,mid)+querySum(id*2+1,mid+1,r);
 69         }
 70     }
 71 long long queryMax(int id,int l,int r)
 72 {
 73     if(l==tree[id].left && r==tree[id].right)
 74         return tree[id].maxt;
 75     int mid=(tree[id].left+tree[id].right)>>1;
 76     long long ret=0;
 77     if(r<=mid)
 78         ret=max(ret,queryMax(id<<1,l,r));
 79     else if(l>=mid+1)
 80         ret=max(ret,queryMax((id<<1)+1,l,r));
 81     else
 82     {
 83         long long a,b;
 84         a=queryMax(id<<1,l,mid);
 85         b=queryMax((id<<1)+1,mid+1,r);
 86         return max(a,b);
 87     }
 88     return ret;
 89 }
 90 int main (void)
 91 {
 92     int n,q;
 93     cin>>n>>q;
 94     memset(a,0,sizeof(a));
 95     build(1,1,n);
 96     while(q--)
 97     {
 98         int t;
 99         scanf("%d",&t);
100         if(t==1)
101         {
102             long long x,y;
103             scanf("%lld%lld",&x,&y);
104             update(1,x,y);
105         }
106         else
107         {
108             int x,y;
109             scanf("%d%d",&x,&y);
110             printf("%lld
",queryMax(1,x,y));
111         }
112     }
113     return 0;
114 }

View Code