HH大神的神题。只能一直膜拜。。。
从线段树起步都是从他的博客里一点一滴的学的。
风格也是仿照他的来的。
然后说题目吧。
题目意思：会有很多波怪兽袭击，然后也有N个英雄。没来一波怪兽就派 编号是 L-R 的英雄去迎敌。
每个英雄都会获得一定的经验（既是 等级 * 每波的经验基数 E） 。最后Q操作就是问你 L-R 段中哪一个英雄的经验最高，并输出最高值。
开始的时候我有点混淆题目。如果他当时还获得的经验足够他升好几级的话，那么当他拿到经验之后，会马上升级，然后升一级以后自己的等级改变了。
把他获得的余下的经验再按新的等级来计算。那么就是雪球越滚越大。然后问了 最小公倍数 学长~~~嚯嚯
自己写的时候，是直接把LAZY (cov 数组) 往下推。然后自己意识到这样的lazy不能直接叠加 因为多次操作之后他的等级就会变。
之前的标记就没用了。 那我又想。那每来一个 cov 我就把之前的 cov往下推。 但是显然 这就如单点更新了。
通过上一段话，应该能明白代码中的 dis 变量作何用处了
dis 是指区间中 那个需求最少经验就可以的英雄 所需要的经验基数。 换句话说 如果这个人都还不能升级的话 那么这个区间内就不会有人能升级了。
那么就可以直接加上 cov 。
如果区间内那个人可以升级。以为这这段区间的某一个人的 lev会发生改变 此时我们就要把这个cov 一直往下推。找到那个变了的人。然后再更新区间。
#include <iostream>
#include <cstdio>
#include <algorithm>
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e
#define maxn 10005
using namespace std;
int exp[maxn<<2],lev[maxn<<2];//区间最大经验 区间最大等级
int cov[maxn<<2],dis[maxn<<2];//lazy 标记数组 dis 如上
int ned[15]={0};
int K;
void pushup(int num)
{
exp[num]=max(exp[num<<1],exp[num<<1|1]);
lev[num]=max(lev[num<<1],lev[num<<1|1]);
dis[num]=min(dis[num<<1],dis[num<<1|1]);
}
int getlev(int ex)//找到经验对应的等级
{
if(ex>=ned[K-1])return K;
for(int i=1;i<=K;i++)
{
if(ex<ned[i])return i;
}
}
void pushdown(int num)
{
if(cov[num])
{
cov[num<<1|1]+=cov[num];
cov[num<<1]+=cov[num];
exp[num<<1]+=(cov[num]*lev[num<<1]);
exp[num<<1|1]+=(cov[num]*lev[num<<1|1]);
dis[num<<1]-=cov[num];
dis[num<<1|1]-=cov[num];
cov[num]=0;
}
}
void build(int num,int s,int e)
{
exp[num]=0;
lev[num]=1;
cov[num]=0;
dis[num]=ned[1];
if(s==e)return;
int mid=(s+e)>>1;
build(lson);
build(rson);
}
void update(int num,int s,int e,int l,int r,int val)
{
int mid=(s+e)>>1;
if(s==e)
{
exp[num]+=lev[num]*val;
lev[num]=getlev(exp[num]);
dis[num]=(ned[lev[num]]-exp[num])/(lev[num])+((ned[lev[num]]-exp[num])%(lev[num])!=0);
return ;
}
if(l<=s && r>=e)
{
if(val<dis[num])
{
exp[num]+=lev[num]*val;
dis[num]-=val;
cov[num]+=val;
return ;
}
else
{
pushdown(num);
update(lson,s,mid,val);
update(rson,mid+1,e,val);
pushup(num);
return ;
}
}
pushdown(num);
if(l<=mid)update(lson,l,r,val);
if(r>mid)update(rson,l,r,val);
pushup(num);
}
int query(int num,int s,int e,int l,int r)
{
if(s>=l && e<=r)
{
return exp[num];
}
pushdown(num);
int mid=(s+e)>>1;
if(r<=mid)return query(lson,l,r);
else if(l>mid)return query(rson,l,r);
else return max(query(lson,l,mid),query(rson,mid+1,r));
}
int main()
{
int T,CASE=1;
scanf("%d",&T);
while(T--)
{
printf("Case %d:\n",CASE++);
int n,qw;
scanf("%d%d%d",&n,&K,&qw);
for(int i=1;i<K;i++)
{
scanf("%d",&ned[i]);
}
ned[K]=1<<30;
build(1,1,n);
while(qw--)
{
char tope[5];
scanf("%s",tope);
if(tope[0]=='W')
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
update(1,1,n,a,b,c);
}
else
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",query(1,1,n,a,b));
}
}
puts("");
}
return 0;
}
/*
5
5 5 999
2 10 15 16
W 1 3 1
W 1 2 1
Q 1 1
*/