题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3954
题目大意：给你n个人初始状态都是1级0经验，有qw次操作，‘W‘操作，放一波怪，区间$[l,r]$的人去砍一波怪，然后对于$k$级的人得到的经验是$e_i\times k$，每级的的经验是$a_i$，升完级后经验保留，最大级是$limt$。‘Q‘操作，询问区间$[l,r]$中经验最多的是多少
Sample Input
2 3 3 5 1 2 W 1 1 1 W 1 2 1 Q 1 3 W 1 3 1 Q 1 3 5 5 8 2 10 15 16 W 5 5 9 W 3 4 5 W 1 1 2 W 2 3 2 Q 3 5 W 1 3 8 Q 1 2 Q 3 5
Sample Output
Case 1: 3 6 Case 2: 9 18 25
emmm，很明显是跑个线段树，不过怎么跑是个关键，我们维护一下每个区间的最大级和最大经验（实际上这两个肯定是同一个人），维护一个最小升级需求。这个最小升级需求我们要全部转化为1级的经验来方便计算。
当这个怪送的经验$e_i$大于等于该区间最小升级需求的时候，我们需要将其更新到根节点，否则打个标记就完事了，其update函数如下：
void update(int l,int r,int rt,int L,int R,int val) { if (l>=L && r<=R){ if (val>=tree[rt].need){//如果能升级，直接更新到根节点 if (l==r){ tree[rt].exp+=tree[rt].level*val; while(tree[rt].exp>=lev_exp[tree[rt].level]) tree[rt].level++; int last=lev_exp[tree[rt].level]-tree[rt].exp; int p=last/tree[rt].level;//把需要的经验全部转换为1级的经验 if (last%tree[rt].level) p++; tree[rt].need=p; } else { if (tree[rt].up) push_down(rt); int mid=(l+r)>>1; if (mid>=L) update(lson,L,R,val); if (mid<R) update(rson,L,R,val); push_up(rt); } } else { tree[rt].up+=val; tree[rt].exp+=tree[rt].level*val; tree[rt].need-=val; } return; } if (tree[rt].up) push_down(rt); int mid=(l+r)>>1; if (mid>=L) update(lson,L,R,val); if (mid<R) update(rson,L,R,val); push_up(rt); }
就是update函数麻烦了点，其他的和普通的线段树并没有太大的差别。
以下是AC代码：
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define lc rt<<1 #define rc rt<<1|1 const int mac=1e4+10; const int inf=1e9+10; struct node { int level,exp,up,need; }tree[mac<<2]; int lev_exp[15]; void build(int l,int r,int rt) { tree[rt].level=1; tree[rt].exp=tree[rt].up=0; tree[rt].need=lev_exp[1]; if (l==r) return; int mid=(l+r)>>1; build(lson);build(rson); } void push_up(int rt) { tree[rt].level=max(tree[lc].level,tree[rc].level); tree[rt].exp=max(tree[lc].exp,tree[rc].exp); tree[rt].need=min(tree[lc].need,tree[rc].need); } void push_down(int rt) { tree[lc].up+=tree[rt].up; tree[rc].up+=tree[rt].up; tree[lc].exp+=tree[lc].level*tree[rt].up; tree[rc].exp+=tree[rc].level*tree[rt].up; tree[lc].need-=tree[rt].up; tree[rc].need-=tree[rt].up; tree[rt].up=0; } void update(int l,int r,int rt,int L,int R,int val) { if (l>=L && r<=R){ if (val>=tree[rt].need){//如果能升级，直接更新到根节点 if (l==r){ tree[rt].exp+=tree[rt].level*val; while(tree[rt].exp>=lev_exp[tree[rt].level]) tree[rt].level++; int last=lev_exp[tree[rt].level]-tree[rt].exp; int p=last/tree[rt].level;//把需要的经验全部转换为1级的经验 if (last%tree[rt].level) p++; tree[rt].need=p; } else { if (tree[rt].up) push_down(rt); int mid=(l+r)>>1; if (mid>=L) update(lson,L,R,val); if (mid<R) update(rson,L,R,val); push_up(rt); } } else { tree[rt].up+=val; tree[rt].exp+=tree[rt].level*val; tree[rt].need-=val; } return; } if (tree[rt].up) push_down(rt); int mid=(l+r)>>1; if (mid>=L) update(lson,L,R,val); if (mid<R) update(rson,L,R,val); push_up(rt); } int query(int l,int r,int rt,int L,int R) { int ans=0; if (l>=L && r<=R) return tree[rt].exp; int mid=(l+r)>>1; if (tree[rt].up) push_down(rt); if (mid>=L) ans=max(ans,query(lson,L,R)); if (mid<R) ans=max(ans,query(rson,L,R)); return ans; } int main() { //freopen("in.txt","r",stdin); int t,Case=0; scanf ("%d",&t); while (t--){ int n,lim,qw; scanf ("%d%d%d",&n,&lim,&qw); lev_exp[lim]=inf; for (int i=1; i<lim; i++) scanf ("%d",&lev_exp[i]); printf("Case %d:\n",++Case); build(1,n,1); while (qw--){ char s[5]; int l,r,e; scanf ("%s%d%d",s,&l,&r); if (s[0]==‘W‘){ scanf ("%d",&e); update(1,n,1,l,r,e); } else printf("%d\n",query(1,n,1,l,r)); } printf("\n"); } return 0; }
HDU - 3954 Level up--打怪升级装备全靠爆（线段树小进阶）
原文：https://www.cnblogs.com/lonely-wind-/p/13276764.html