又是一开始觉得的水题，结果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=<<;
const double Pi=acos(-1.0);
const int Max=<<;
int segtr[][Max],upn[Max];//分别记录十个等级的最大值，意为建立10棵树
int lev[];//k比较小，则可以开数组记录每一等级的最大经验值 以此来看是否有人升级 有人升级就更新到叶子节点 最大等级k比较小所以不会超时
int nmax(int a,int b)
{
return a>b?a:b;
}
void Upnow(int now,int next,int k)//上更新 关键
{
for(int i=; i<k; i++)
segtr[i][now]=nmax(segtr[i][next],segtr[i][next|]);
return;
}
void Create(int sta,int enn,int now,int k)
{
upn[now]=;
segtr[][now]=;
for(int i=; i<k; i++)//这一段没有这个等级
segtr[i][now]=-;
if(sta==enn)
return;
int mid=dir(sta+enn,);
int next=mul(now,);
Create(sta,mid,next,k);
Create(mid+,enn,next|,k);
return;
}
int Levup(int i,int now,int k,int z)//判断升级函数
{
int j,flag=;
if(segtr[i][now]!=-)
{
segtr[i][now]+=(i+)*z;
j=i;
while(segtr[j][now]>=lev[j])//可能不止升一级
{
segtr[j+][now]=nmax(segtr[j+][now],segtr[j][now]);
j++;
}
if(segtr[i][now]>=lev[i])
{
segtr[i][now]=-;//一定更新到叶子，所以直接赋值为-1，**过后一定会回溯更新父节点**
flag=;
}
}
return flag;
}
void Downow(int now,int next,int k)//lazy更新
{
if(upn[now])
{
upn[next]+=upn[now];
upn[next|]+=upn[now];
for(int i=k-; i>=; i--)
{
Levup(i,next,k,upn[now]);//每个孩子节点的10个值要处理lazy操作
Levup(i,next|,k,upn[now]);
}
upn[now]=;
}
return;
}
int Update(int sta,int enn,int now,int x,int y,int z,int k)
{
if(sta>=x&&enn<=y)
{
int flag=;
for(int i=k-; i>=; i--)
flag|=Levup(i,now,k,z);//升级了就一定继续更新，不返回
if(!flag||sta==enn)//没人升级或者已经更新到叶子节点
{
int manx=;
for(int i=; i<k; i++)
manx=nmax(manx,segtr[i][now]);
upn[now]+=z;
return manx;
}
}
int mid=dir(sta+enn,);
int next=mul(now,);
Downow(now,next,k);
int ans=;
if(mid>=x)//这儿有时可以做文章
ans=nmax(ans,Update(sta,mid,next,x,y,z,k));
if(mid<y)
ans=nmax(ans,Update(mid+,enn,next|,x,y,z,k));
Upnow(now,next,k);
return ans;
}
int main()
{
int t,n,k,q,coun=;
int lef,rig,ei;
char str[];
scanf("%d",&t);
while(t--)
{
scanf("%d %d %d",&n,&k,&q);
for(int i=; i<k-; i++)
scanf("%d",&lev[i]);
lev[k-]=Inf;//不能再升级
Create(,n,,k);
printf("Case %d:\n",++coun);
for(int i=; i<q; i++)
{
scanf("%s",str);
if(str[]=='W')
{
scanf("%d %d %d",&lef,&rig,&ei);
Update(,n,,lef,rig,ei,k);
}
else
{
scanf("%d %d",&lef,&rig);
printf("%d\n",Update(,n,,lef,rig,,k));
}
}
printf("\n");
}
return ;
}