2015
04-14

# Level up

Level up is the task of all online games. It’s very boooooooooring. There is only level up in those games, except level up.
In a online game, there are N heroes numbered id from 1 to N, each begins with level 1 and 0 Experience. They need to kill monsters to get Exp and level up.

There are many waves of monsters, each wave, the heroes with id from li to ri will come to kill monsters and those hero with level k will get ei*k Exp. If one hero’s Exp reach Needk then the hero level up to level k immediately.
After some waves, I will query the maximum Exp from li to ri.
Now giving the information of each wave and Needk, please tell me the answer of my query.

The first line is a number T(1<=T<=30), represents the number of case. The next T blocks follow each indicates a case.
The first line of each case contains three integers N(1<=N<=10000), K(2<=K<=10) and QW(1<=QW<=10000)each represent hero number, the MAX level and querys/waves number.
Then a line with K -1 integers, Need2, Need3…Needk.(1 <= Need2 < Need3 < … < Needk <= 10000).
Then QW lines follow, each line start with ‘W’ contains three integers li ri ei (1<=li<=ri<=N , 1<=ei<=10000); each line start with ‘Q’ contains two integers li ri (1<=li<=ri<=N).

The first line is a number T(1<=T<=30), represents the number of case. The next T blocks follow each indicates a case.
The first line of each case contains three integers N(1<=N<=10000), K(2<=K<=10) and QW(1<=QW<=10000)each represent hero number, the MAX level and querys/waves number.
Then a line with K -1 integers, Need2, Need3…Needk.(1 <= Need2 < Need3 < … < Needk <= 10000).
Then QW lines follow, each line start with ‘W’ contains three integers li ri ei (1<=li<=ri<=N , 1<=ei<=10000); each line start with ‘Q’ contains two integers li ri (1<=li<=ri<=N).

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

Case 1:
3
6

Case 2:
9
18
25
Hint
Case 1:
At first ,the information of each hero is 0(1),0(1),0(1) [Exp(level)]
After first wave, 1(2),0(1),0(1);
After second wave, 3(3),1(2),0(1);
After third wave, 6(3),3(3),1(2);
Case 2:
The information of each hero finally:
18(5) 18(5) 25(5) 5(2) 9(2)


HDU 3954 level up

HH的神题，想当初阿里巴巴这比赛是第一次参加的网上的比赛，还是组队的。结果被HH的一套神题完虐

1、第一位开启“网吧通宵刷题模式”的队员（注：当时大一不允许带电脑，在一片充满游戏、电影以及美女图片的屏幕中能看到有人敲代码，你不觉得很酷吗？），此热情深深影响一届人；
2、第一位在第一学期就担任集训队副队长的队员；
3、第一位在大一就获得省赛金牌的队员（大学之前0基础）；
4、第一位本科期间入围百度之星总决赛的队员（2010、2011年2次入围百度之星总决赛）；
5、第一位大二就参加World Final的队员；
6、第一位2度参加World Final的队员（大二、大三参加World Final，无奈大四只能退役）；
7、第一位带领队伍省赛捧杯的队员（2011年浙江省第8届省赛）；
8、第一位大学4年3夺省赛金牌的队员；
……

/*
ID:cxlove
PROB:hdu 3954
DATA:2012.5.8
HINT:线段树
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#define LL long long
using namespace std;
int sum[15],n,k,q;
struct Line{
int left,right,mid;
int exp,level;   //区间最大的经验，等级
int min_dist,lazy;   //区间升级所需的最少经验基数，懒惰标记
}L[50005];
//建树
void bulid(int step,int l,int r){
L[step].left=l;
L[step].right=r;
L[step].mid=(l+r)/2;
L[step].min_dist=sum[1];    //初始等级为1，所以经验基数便是sum[1]/1
L[step].exp=0;         //初始经验为0
L[step].level=1;         //初始等级为1
L[step].lazy=0;
if(l==r)
return;
bulid(2*step,l,(l+r)/2);
bulid(2*step+1,(l+r)/2+1,r);
}
//向下更新，lazy更新到子节点
void PushDown(int step){
L[2*step].exp+=L[step].lazy*L[2*step].level;
L[2*step].min_dist-=L[step].lazy;
L[2*step].lazy+=L[step].lazy;

L[2*step+1].exp+=L[step].lazy*L[2*step+1].level;
L[2*step+1].min_dist-=L[step].lazy;
L[2*step+1].lazy+=L[step].lazy;

L[step].lazy=0;
}
//向上更新，更新了子节点后，更新父节点
void PushUp(int step){
L[step].exp=max(L[2*step].exp,L[2*step+1].exp);
L[step].level=max(L[2*step].level,L[2*step+1].level);
L[step].min_dist=min(L[2*step].min_dist,L[2*step+1].min_dist);
}
//更新操作
void update(int step,int l,int r,int e){
//叶子节点
if(L[step].left==L[step].right){
L[step].exp+=L[step].level*e;
while(L[step].exp>=sum[L[step].level])
L[step].level++;
//计算还需要多少经验基数升级
L[step].min_dist=(sum[L[step].level]-L[step].exp)/L[step].level+((sum[L[step].level]-L[step].exp)%L[step].level!=0);
return ;
}
if(L[step].left==l&&L[step].right==r){
//区间内有英雄要升级了
if(e>=L[step].min_dist){
//lazy更新子节点
PushDown(step);
//更新子区间
update(2*step,l,(l+r)/2,e);
update(2*step+1,(l+r)/2+1,r,e);
//更新父节点
PushUp(step);
}
//当前没有英雄升级
else{
L[step].exp+=L[step].level*e;
L[step].min_dist-=e;
L[step].lazy+=e;
}
return ;
}
//向下更新
if(L[step].lazy)
PushDown(step);
if(r<=L[step].mid)
update(2*step,l,r,e);
else if(l>L[step].mid)
update(2*step+1,l,r,e);
else{
update(2*step,l,L[step].mid,e);
update(2*step+1,L[step].mid+1,r,e);
}
PushUp(step);
}
int query(int step,int l,int r){
if(L[step].left==l&&L[step].right==r)
return L[step].exp;
if(L[step].lazy)
PushDown(step);
if(r<=L[step].mid)
return query(2*step,l,r);
else if(l>L[step].mid)
return query(2*step+1,l,r);
else
return max(query(2*step,l,L[step].mid),query(2*step+1,L[step].mid+1,r));
}
int main(){
int t,cas=0;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&k,&q);
for(int i=1;i<k;i++)
scanf("%d",&sum[i]);
sum[k]=1<<30;   //这里不可少
printf("Case %d:\n",++cas);
bulid(1,1,n);
while(q--){
char str[10];
int x,y,e;
scanf("%s",str);
if(str[0]=='W'){
scanf("%d%d%d",&x,&y,&e);
update(1,x,y,e);
}
else{
scanf("%d%d",&x,&y);
printf("%d\n",query(1,x,y));
}
}
printf("\n");
}
return 0;
}


1. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧