HDU 3954 Level up（多颗线段树+lazy操作）-白红宇

HDU 3954 Level up（多颗线段树+lazy操作）

阅读量：6607 次

发布时间：2019-06-24

本文共 1951 字，大约阅读时间需要 6 分钟。

又是一开始觉得的水题，结果GG了好久的东西。。。

题意是给你n个英雄，每个英雄开始为1级经验为0，最多可以升到k级并且经验一直叠加，每一级都有一个经验值上限，达到就升级。接着给你两种操作：

W li ri ei：从第li到第ri个增加经验基数ei，注意这儿ei还需要乘以级数才是真正增加的经验，还有就是先在此等级下增加此等级倍数的经验，然后再判断升级情况

Q li ri ：在第li到第ri个查找经验最多的值

　　记录最大值嘛，不过因为级数控制增加的倍数，也就是说区间更新时，多次更新标记得到的只是基数ei，倍数不确定。所以可以从级数k（小于11）入手，建立10棵线段树每个等级一颗，然后没有这个等级就记为-1，有就记录最大经验值。但是还有一个问题就是此点代表的区间有些人升级，有些人没升级，所以我们把每个会升级的节点都更新到底（每个节点最大经验值就在于判断这一段是否有人升级），最多就k*n次。最后要注意一个问题，就是当增加ei的时候，可能不止升一级。

　　这儿牵扯到lazy操作的修改模板（其实我的模板虽然基本一样，但是我还是经常会改变写法的）

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;#define eps 1E-8/*注意可能会有输出-0.000*/#define Sgn(x) (x<-eps? -1 :x
                 
                   0.0 ? x+eps : x-eps)//浮点数转化#define zero(x) (((x)>0?(x):-(x))
                  
                   >b)typedef long long ll;typedef unsigned long long ull;const int Inf=1<<30;const double Pi=acos(-1.0);const int Max=10100<<2;int segtr[10][Max],upn[Max];//分别记录十个等级的最大值，意为建立10棵树int lev[15];//k比较小，则可以开数组记录每一等级的最大经验值 以此来看是否有人升级 有人升级就更新到叶子节点 最大等级k比较小所以不会超时int nmax(int a,int b){ return a>b?a:b;}void Upnow(int now,int next,int k)//上更新 关键{ for(int i=0; i
                   
                    =lev[j])//可能不止升一级 { segtr[j+1][now]=nmax(segtr[j+1][now],segtr[j][now]); j++; } if(segtr[i][now]>=lev[i]) { segtr[i][now]=-1;//一定更新到叶子，所以直接赋值为-1，**过后一定会回溯更新父节点** flag=1; } } return flag;}void Downow(int now,int next,int k)//lazy更新{ if(upn[now]) { upn[next]+=upn[now]; upn[next|1]+=upn[now]; for(int i=k-1; i>=0; i--) { Levup(i,next,k,upn[now]);//每个孩子节点的10个值要处理lazy操作 Levup(i,next|1,k,upn[now]); } upn[now]=0; } return;}int Update(int sta,int enn,int now,int x,int y,int z,int k){ if(sta>=x&&enn<=y) { int flag=0; for(int i=k-1; i>=0; i--) flag|=Levup(i,now,k,z);//升级了就一定继续更新，不返回 if(!flag||sta==enn)//没人升级或者已经更新到叶子节点 { int manx=0; for(int i=0; i
                    
                     =x)//这儿有时可以做文章 ans=nmax(ans,Update(sta,mid,next,x,y,z,k)); if(mid

转载于:https://www.cnblogs.com/zhuanzhuruyi/p/5863699.html

你可能感兴趣的文章