hdu 3954 level up 线段树区间维护

不绕弯子，线段树区间值维护。

每个区间应记录的值，lazy,val[12],val数组当中记录的是该区间当中每一个级数最大的经验值，如果此时经验值能够使得英雄升级，在一段区间当中有某个结点需要更新，此时我们如果用update操作的话，就要更新到最底层，那么此时线段树就没有意义，所以现在我们必须要控制一下，只更新升级了的区间，那么我们就避免了更新一些不必要的点，因为当区间中的英雄级数不变的时候，经验累加的规则是不会改变的，所以只要精心敲一下其中的pushdown就ok了。

在向下的更新当中，最终要的是，更新了底层的话，上层也必须要更新，所以要特别注意，总结线段树的经验，其实最要紧的就是心要够细，如果心浮气躁还是先静一下再敲吧。。。

View Code

  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #include<string.h>
  5 
  6 const int N = 11111;
  7 const int INF=((1<<30)-1);
  8 
  9 struct node
 10 {
 11     int l,r;
 12     int lazy;
 13     int val[12];
 14 } tre[N<<2];
 15 
 16 int le[12],k;
 17 
 18 int upgrade(int lev,int ep)
 19 {
 20     while (lev<k)
 21     {
 22         if (ep<le[lev]) break;
 23         else lev++;
 24     }
 25     return lev;
 26 }
 27 
 28 int Max(int a,int b)
 29 {
 30     return a>b?a:b;
 31 }
 32 
 33 void PushUp(int rt)
 34 {
 35     for(int i=1; i<=k; i++)
 36         tre[rt].val[i]=Max(tre[rt<<1].val[i],tre[rt<<1|1].val[i]);
 37 }
 38 
 39 void build(int rt,int l,int r)
 40 {
 41     tre[rt].l=l; tre[rt].r=r;
 42     memset(tre[rt].val,-1,sizeof(tre[rt].val));
 43     tre[rt].lazy=tre[rt].val[1]=0;
 44     if(l==r) return ;
 45     int m=(r+l)>>1;
 46     build(rt<<1,l,m);
 47     build(rt<<1|1,m+1,r);
 48 }
 49 
 50 void PushDown(int rt)
 51 {
 52     if (tre[rt].l>=tre[rt].r) return ;
 53     if(tre[rt].lazy>0)
 54     {
 55         int t1=rt<<1;
 56         int t2=t1|1;
 57         int flag1=0,flag2=0;
 58         int v=tre[rt].lazy;
 59         tre[t1].lazy+=v;
 60         tre[t2].lazy+=v;
 61         tre[rt].lazy=0;
 62         for(int i=k; i>0; i--)
 63         {
 64             if(tre[t1].val[i]>=0)
 65             {
 66                 tre[t1].val[i]+=i*v;
 67                 if(tre[t1].val[i]>=le[i]&&i!=k)
 68                 {

 69                     int tmp=upgrade(i,tre[t1].val[i]);
 70                     if (tmp!=i)
 71                     {
 72                         tre[t1].val[tmp]=Max(tre[t1].val[tmp],tre[t1].val[i]);
 73                         tre[t1].val[i]=-1;
 74                         flag1=1;
 75                     }
 76                 }
 77             }
 78             if(tre[t2].val[i]>=0)
 79             {
 80                 tre[t2].val[i]+=i*v;
 81                 if(tre[t2].val[i]>=le[i]&&i!=k)
 82                 {
 83                     int tmp=upgrade(i,tre[t2].val[i]);
 84                     if (tmp!=i)
 85                     {
 86                         tre[t2].val[tmp]=Max(tre[t2].val[tmp],tre[t2].val[i]);
 87                         tre[t2].val[i]=-1;
 88                         flag2=1;
 89                     }
 90                 }
 91             }
 92         }
 93         if(flag1) PushDown(t1);
 94         if(flag2) PushDown(t2);
 95         PushUp(rt);
 96     }
 97 }
 98 
 99 void update(int rt,int l,int r,int L,int R,int v)
100 {
101     if(L<=l&&r<=R)
102     {
103         int flag=0;
104         for (int i=k; i>0; i--)
105         {
106             if (tre[rt].val[i]>=0)
107             {
108                 tre[rt].val[i]+=i*v;
109                 if (tre[rt].val[i]>=le[i]&&i!=k)
110                 {
111                     flag=1;
112                     int tmp=upgrade(i,tre[rt].val[i]);
113                     if (tmp!=i)
114                     {
115                      tre[rt].val[tmp]=Max(tre[rt].val[tmp],tre[rt].val[i]);
116                      tre[rt].val[i]=-1;
117                     }
118                 }
119             }
120         }
121         tre[rt].lazy+=v;
122         if (flag) PushDown(rt);
123         return ;
124     }
125     PushDown(rt);
126     int m=(r+l)>>1;
127     if(L<=m)update(rt<<1,l,m,L,R,v);
128     if(R>m) update(rt<<1|1,m+1,r,L,R,v);
129     PushUp(rt);
130 }
131 
132 int query(int rt,int l,int r,int L,int R)
133 {
134     if(L<=l&&r<=R)
135     {
136         for (int i=k; i>0; i--)
137         {
138             if (tre[rt].val[i]>=0) return tre[rt].val[i];
139         }
140     }
141     if (l==r) return 0;
142     PushDown(rt);
143     int m=(r+l)>>1;
144     int ans=0;
145     if(L<=m)ans=Max(ans,query(rt<<1,l,m,L,R));
146     if(R>m) ans=Max(ans,query(rt<<1|1,m+1,r,L,R));
147     return ans;
148 }
149 
150 int main()
151 {
152     int t,n,m,a,b,v,T=0;
153     scanf("%d",&t);
154     char temp[5];
155     while(t--)
156     {
157         scanf("%d%d%d",&n,&k,&m);
158         build(1,1,n);
159         for(int i=1; i<k; i++)scanf("%d",&le[i]);
160         le[k]=INF;
161         printf("Case %d:\n",++T);
162         for(int i=0; i<m; i++)
163         {
164             scanf("%s",&temp);
165             if(temp[0]=='W')
166             {
167                 scanf("%d%d%d",&a,&b,&v);
168                 update(1,1,n,a,b,v);
169             }
170             else
171             {
172                 scanf("%d%d",&a,&b);
173                 int tmp=query(1,1,n,a,b);
174                 printf("%d\n",tmp);
175             }
176         }
177         printf("\n");
178     }
179     return 0;
180 }