又是一开始觉得的水题，结果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<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<stdlib.h> #include<iostream> #include<algorithm> using namespace std; #define eps 1E-8 /*注意可能会有输出-0.000*/ #define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型 #define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化 #define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0 #define mul(a,b) (a<<b) #define dir(a,b) (a>>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<k; i++) segtr[i][now]=nmax(segtr[i][next],segtr[i][next|1]); return; } void Create(int sta,int enn,int now,int k) { upn[now]=0; segtr[0][now]=0; for(int i=1; i<k; i++)//这一段没有这个等级 segtr[i][now]=-1; if(sta==enn) return; int mid=dir(sta+enn,1); int next=mul(now,1); Create(sta,mid,next,k); Create(mid+1,enn,next|1,k); return; } int Levup(int i,int now,int k,int z)//判断升级函数 { int j,flag=0; if(segtr[i][now]!=-1) { segtr[i][now]+=(i+1)*z; j=i; while(segtr[j][now]>=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<k; i++) manx=nmax(manx,segtr[i][now]); upn[now]+=z; return manx; } } int mid=dir(sta+enn,1); int next=mul(now,1); Downow(now,next,k); int ans=0; if(mid>=x)//这儿有时可以做文章 ans=nmax(ans,Update(sta,mid,next,x,y,z,k)); if(mid<y) ans=nmax(ans,Update(mid+1,enn,next|1,x,y,z,k)); Upnow(now,next,k); return ans; } int main() { int t,n,k,q,coun=0; int lef,rig,ei; char str[10]; scanf("%d",&t); while(t--) { scanf("%d %d %d",&n,&k,&q); for(int i=0; i<k-1; i++) scanf("%d",&lev[i]); lev[k-1]=Inf;//不能再升级 Create(1,n,1,k); printf("Case %d: ",++coun); for(int i=0; i<q; i++) { scanf("%s",str); if(str[0]=='W') { scanf("%d %d %d",&lef,&rig,&ei); Update(1,n,1,lef,rig,ei,k); } else { scanf("%d %d",&lef,&rig); printf("%d ",Update(1,n,1,lef,rig,0,k)); } } printf(" "); } return 0; }