学步园

http://www.notonlysuccess.com/index.php/alibaba/

做不出来，参考了not。。。。的解释，懂了，敲完发现，与他的代码几乎一样。。。。。

题意很简单,成段更新,成段询问,但是更新却和一般的线段树大不一样,每个点虽然接收到相同的信息,但是由于本身不同,最终得到的值也是不同的.用一般的延迟操作就搞不定了.

突破点在K,范围很小,只有10,可以考虑每次有人升级的时候,就递归的找下去,将这个人进行升级操作.由于找到某个人只需要logn的复杂度,每个人最多升k次,所以n个人的复杂度是O(nklogn)

用了两个辅助数组add[maxn]和MAX[maxk][maxn],add用于记录延迟标记,MAX[k]表示该区间等级为k的最大经验值.初始化add,MAX[1]为0,其他为-1,表示无人在这个等级.当MAX[k]的值大于等于Needk时,就对这个区间进行升级操作,和线段树操作一样递归的将这个区间能升级的人全部升级.

单次操作可能会是nlogn(每个人都升级),但是平均下来还是只有nklogn.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 11111;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int MAX[11][maxn<<2];
int add[maxn<<2];
int K,n;
int need[maxn];
int max(int a,int b){
return a>b?a:b;
}
void pushup(int rt){
for(int i=1;i<=K;i++){
        MAX[i][rt]=max(MAX[i][rt<<1],MAX[i][rt<<1|1]);
    }
}
void pushdown(int rt){
if(add[rt]){    
        add[rt<<1]+=add[rt];
        add[rt<<1|1]+=add[rt];
for(int i=1;i<=K;i++){
if(MAX[i][rt<<1]!=-1)
                MAX[i][rt<<1]+=add[rt]*i;
if(MAX[i][rt<<1|1]!=-1)
                MAX[i][rt<<1|1]+=add[rt]*i;

        }
        add[rt]=0;
    }
}
void levelup(int i,int l,int r,int rt) {
if (l == r) {
while (i < K) {
if (MAX[i][rt] < need[i]) break;
            MAX[i+1][rt] = MAX[i][rt];
            MAX[i][rt] = -1;
            i ++;
        }
return ;
    }
    pushdown(rt);
int m = (l + r) >> 1;
if (MAX[i][rt<<1] >= need[i]) levelup(i , lson);
if (MAX[i][rt<<1|1] >= need[i]) levelup(i , rson);
    pushup(rt);
}
void update(int L,int R,int c,int l,int r,int rt) {
if (L <= l && r <= R) {
        add[rt] += c;
for (int i = K ; i >= 1 ; i --) {
if (MAX[i][rt] != -1) MAX[i][rt] += c * i;
if (i < K && MAX[i][rt] >= need[i]) {
                levelup(i , l , r , rt);
            }
        }
return ;
    }
    pushdown(rt);
int m = (l + r) >> 1;
if (L <= m) update(L , R , c , lson);
if (m < R) update(L , R , c , rson);
    pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
if(L<=l&&r<=R){
for(int i=K;i>=1;i--)
        {
if(MAX[i][rt]!=-1)
return MAX[i][rt];
        }
    }
    pushdown(rt);
int m=(l+r)>>1;
int ret=0;
if(L<=m) ret=max(ret,query(L,R,lson));
if(R>m) ret=max(ret,query(L,R,rson));
return ret;
}
int main(){
int t,ca=1,i,j,q,a,b,c;
char op[5];
    scanf("%d",&t);
while(t--){
        scanf("%d%d%d",&n,&K,&q);
for(i=1;i<K;i++) scanf("%d",&need[i]);
        memset(add,0,sizeof(add));
        memset(MAX[1],0,sizeof(MAX[1]));
for(i=2;i<=K;i++){
            memset(MAX[i],-1,sizeof(MAX[i]));
        }
        printf("Case %d:\n",ca++);
while(q--){
            scanf("%s",op);
if(op[0]=='W'){
                scanf("%d%d%d",&a,&b,&c);
                update(a,b,c,1,n,1);
            }
else {
                scanf("%d%d",&a,&b);
                printf("%d\n",query(a,b,1,n,1));
            }
        }
         puts("");
    }
return 0;
}