HDU 3954 区间更新区间查询 打怪升级

#include<string.h>  
#include<stdio.h>  
#include<queue>  
#include<math.h>  
  
#define inf 33554432  
#define L(x) (x<<1)  
#define R(x) (x<<1|1)  
#define Mid(x,y) ((x+y)>>1)  
#define ll int  
#define N 10010  
using namespace std;  
  
inline int Max(int a,int b){return a<b?b:a;}  
inline int Min(int a,int b){return a>b?b:a;}  
  
struct node{  
    int l, r;  
    int grade, ex;//grade 为区间中最高等级 ex为区间中最大的 英雄的总经验(非经验条经验)   
    int lazy;//表示打怪获得经验  
    int need;//区间中升级所需最少经验的英雄 所需的打怪经验  
}tree[N*8];  
  
int expe[12], K;  
void updata_grade(int id){  
    for(int i = tree[id].grade; i < K;i++)  
        if(tree[id].ex >= expe[i])  
            tree[id].grade = i + 1;  
}  
  
void updata_down(int id){  
    tree[L(id)].ex += tree[L(id)].grade*tree[id].lazy;  
    tree[L(id)].lazy += tree[id].lazy;  
    tree[L(id)].need -= tree[id].lazy;  
  
    tree[R(id)].ex += tree[R(id)].grade*tree[id].lazy;  
    tree[R(id)].lazy += tree[id].lazy;  
    tree[R(id)].need -= tree[id].lazy;  
  
    tree[id].lazy = 0;  
}  
void updata_up(int id){  
    tree[id].ex = Max(tree[L(id)].ex, tree[R(id)].ex);  
    tree[id].grade = Max(tree[L(id)].grade, tree[R(id)].grade);  
    tree[id].need = Min(tree[L(id)].need, tree[R(id)].need);  
  
}  
void build(int l, int r, int id){  
    tree[id].l = l , tree[id].r = r;  
    tree[id].ex = 0;  
    tree[id].grade = 1;  
    tree[id].lazy = 0;  
    tree[id].need = expe[1];  
  
    if(l == r)return ;  
    int mid = Mid(l,r);  
    build(l,   mid, L(id));  
    build(mid+1, r, R(id));  
}  
void updata(int l, int r, int id, int Exp){  
    updata_down(id);  
    if(tree[id].l == tree[id].r)  
        {  
            tree[id].ex += Exp* tree[id].grade;  
            updata_grade(id);  
            tree[id].need =(expe[tree[id].grade]-tree[id].ex)/tree[id].grade+((expe[tree[id].grade]-tree[id].ex)%tree[id].grade!=0);    
            return;  
        }  
    if(l == tree[id].l && tree[id].r == r)  
    {  
        if(tree[id].need > Exp) //获得打怪经验后区间内英雄都不会升级  
        {  
            tree[id].lazy += Exp;  
            tree[id].ex += tree[id].grade*Exp;  
            tree[id].need -= Exp;  
            return ;  
        }  
        updata_down(id);//有英雄要升级了  
        updata(tree[L(id)].l, tree[L(id)].r, L(id), Exp);  
        updata(tree[R(id)].l, tree[R(id)].r, R(id), Exp);  
        updata_up(id);  
        return ;  
    }  
  
    int mid = Mid(tree[id].l, tree[id].r);  
    if(r<=mid) updata(l, r, L(id), Exp);  
    else if(l>mid)updata(l, r, R(id), Exp);  
    else  
    {  
        updata(l, mid, L(id), Exp);  
        updata(mid+1, r, R(id), Exp);  
    }  
    updata_up(id); ///  
}  
int query(int l, int r, int id){  
    if(l == tree[id].l && tree[id].r == r)  
    {  
        return tree[id].ex;  
    }  
  
    updata_down(id);  
    int mid = Mid(tree[id].l, tree[id].r);  
    if(r<=mid) return query(l, r, L(id));  
    else if(mid<l) return query(l, r, R(id));  
    else   
        return Max( query(l, mid, L(id)), query(mid+1, r, R(id)));  
}  
  
  
int main(){  
    expe[0] = 0;  
    int T, Cas = 1;scanf("%d",&T);  
    int n, que, i, u, v, EXP;  
  
    while(T--){  
        scanf("%d %d %d",&n,&K,&que);  
        for(i = 1; i < K; i++)scanf("%d",&expe[i]);   
        expe[K] = inf;  
  
        build(1, n, 1);  
        printf("Case %d:\n",Cas++);  
        while(que--)  
        {  
            char c = 'h'; while(c!='W' && c!='Q')c = getchar();  
            scanf("%d %d",&u,&v);  
            if(c == 'W')  
            { scanf("%d",&EXP); updata(u, v, 1, EXP); }  
            else   
                printf("%d\n",query(u, v, 1));  
        }  
        printf("\n");  
    }  
    return 0;  
}