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
*/
