[1]

#include<stdio.h>#include<stdio.h>#include<stdio.h>
#include<algorithm>
#define go(i,a,b) for(int i=a;i<=b;i++)
using namespace std;const int N=30003;char c;bool leaf[N];
int n,k,q,T,Exp[20],t,lch[N],rch[N],sz,d,ans,need[N],Max[N],level[N],lazy[N];
inline void keep(int u,int val);
inline void Down(int u)
{
      if(!lazy[u])return;
      keep(lch[u],lazy[u]);
      keep(rch[u],lazy[u]);lazy[u]=0;
}
inline void Up(int u)
{
      Max[u]=max(Max[lch[u]],Max[rch[u]]);
      level[u]=max(level[lch[u]],level[rch[u]]);
      need[u]=min(need[lch[u]],need[rch[u]]);
}
inline void keep(int u,int val)
{ 
      lazy[u]+=val;need[u]-=val;Max[u]+=level[u]*val;
      if(need[u]>0)return; 
      if(leaf[u]){while(Max[u]>=Exp[level[u]])level[u]++;
      int gap=Exp[level[u]]-Max[u];need[u]=gap/level[u]+(gap%level[u]>0);
      }else Down(u),Up(u);
}
inline void update(int u,int l,int r,int L,int R)
{
      if(L<=l&&r<=R){keep(u,d);return;}
      int M=l+r>>1;Down(u);
      if(L<=M)update(lch[u],l,M,L,R);
      if(R>M)update(rch[u],M+1,r,L,R);Up(u);
}
inline void query(int u,int l,int r,int L,int R)
{
      if(L<=l&&r<=R){ans=max(ans,Max[u]);return;}
      int M=l+r>>1;Down(u);
      if(L<=M)query(lch[u],l,M,L,R);
      if(R>M)query(rch[u],M+1,r,L,R);Up(u);
}
inline void build(int& u,int l,int r)
{
      u=++sz;int M=l+r>>1;leaf[u]=0;lazy[u]=Max[u]=0;
      if(l==r){need[u]=Exp[1];leaf[u]=level[u]=1;return;}
      build(lch[u],l,M);build(rch[u],M+1,r);Up(u);
}
int main(){scanf("%d",&T);t=T;while(T--&&scanf("%d%d%d",&n,&k,&q))
{ 
      go(i,1,k-1)scanf("%d",&Exp[i]);Exp[k]=1e9;
      sz=0;int root;build(root,1,n); 
      printf("Case %d:\n",t-T);
      while(q--&&scanf(" %c",&c))
      {
            int l,r;
            if(c==’W’)scanf("%d%d%d",&l,&r,&d),update(root,1,n,l,r);
            if(c==’Q’)scanf("%d%d",&l,&r),ans=0,query(root,1,n,l,r),printf("%d\n",ans);
      }
puts("");}return 0;}//Paul_Guderian

[1]