学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3954

代码风格：www.notonlysuccess.com

题目大意：

有n个人站一排，有m次操作，每个人最多可以到达k级，给出升级所需到达的经验

操作：w——【a，b】区间每个人都会获得（等级level * 经验k）的经验，q——求区间【a，b】内经验值最多的人有多少经验。

如果经验满足升级条件，那么人物的等级level将会升级。最高等级为k级，人物的初始等级为1级

算法：线段树

思路：如果区间有可以升级的，更新到底~~每个结点记录升级所需要的最少【基】经验，最大等级，最大经验；在PushUp中返回最大等级，最大经验，以及最小基经验，在pushdown中下放add，下放基经验，下放sum[rt << 1] += add[rt] * level[rt << 1];

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

#define lson l, m, rt << 1
#define rson m+1, r, rt << 1 | 1
#define mid int m = (l+r) >> 1

int n, mm, K;
int lev[15];
int level[80000], sum[80000], les[80000], add[80000];

int minz(int a, int b)
{
    return a < b ? a : b; 
}

int maxz(int a, int b)
{
    return a > b ? a : b;
}

void PushUp(int rt)
{
    les[rt] = minz(les[rt << 1], les[rt << 1 | 1]);
    sum[rt] = maxz(sum[rt << 1], sum[rt << 1 | 1]);
    level[rt] =  maxz(level[rt << 1], level[rt << 1 | 1]);
}

void PushDown(int rt)
{
    if(add[rt])
    {
        add[rt << 1] += add[rt];
        add[rt << 1 | 1] += add[rt];
        les[rt << 1] -= add[rt];
        les[rt << 1 | 1] -= add[rt];
        sum[rt << 1] += add[rt] * level[rt << 1];
        sum[rt << 1 | 1] += add[rt] * level[rt << 1 | 1];
        add[rt] = 0;
    }
}

void build(int l, int r, int rt)
{
    level[rt] = 1;
    sum[rt] = 0;
    les[rt] = lev[1];
    if(l == r)
    {
        return ;
    }
    mid ;
    build(lson);
    build(rson);
}

void update(int L, int R, int k, int l, int r, int rt)
{
//    printf("rt = %d\n", rt);
    if(L <= l && r <= R)
    {
        if(les[rt] <= k && l != r)
        {
            PushDown(rt);
            mid ;
            update(L, R, k, lson);
            update(L, R, k, rson);
            PushUp(rt);
        }//×ÓÊ÷Éý¼¶
        else if(l == r)
        {
            sum[rt] += k * level[rt];
            int i = level[rt];
            while(lev[i ++] <= sum[rt])
                level[rt] = i;
            les[rt] = lev[level[rt]] - sum[rt];
            les[rt] = (les[rt] - 1) / level[rt] + 1;//ÐèÒª×îÉÙ¾­Ñé
        }
        else
        {
            sum[rt] += k * level[rt];
            add[rt] += k;
            les[rt] -= k;
        }
        return ;
    }
    mid ;
    PushDown(rt);
    if(L <= m)
        update(L, R, k, lson);
    if(m < R)
        update(L, R, k, rson);
    PushUp(rt);
}

int query(int L, int R, int l, int r, int rt)
{
    if(L <= l && r <= R)
    {
        return sum[rt];
    }
    mid ;
    int ret = 0;
    PushDown(rt);
    if(L <= m)
        ret = maxz(ret, query(L, R, lson));
    if(m < R) ret = maxz(ret, query(L, R, rson));
    return ret ;
}


int main()
{
    int T;
    scanf("%d", &T);
    int ica = 1;
    while(T --)
    {
        printf("Case %d:\n", ica ++);
        scanf("%d%d%d", &n, &K, &mm);
        memset(add, 0, sizeof(add));
        lev[0] = 0;
        int i;
        for(i = 1; i < K; i ++)
        {
            scanf("%d", &lev[i]);
        }
        lev[i] = 0x7fffffff;
        build(1, n, 1);
        int a, b, c;
        char op[4];
        while(mm --)
        {
            scanf("%s%d%d", op, &a, &b);
            if(op[0] == 'W')
            {
                scanf("%d", &c);
                update(a, b, c, 1, n, 1);
            }
            else
            {
                printf("%d\n", query(a, b, 1, n, 1));
            }
        }
        printf("\n");
    }
    return 0;
}