首页 > ACM题库 > HDU-杭电 > HDU 3954-Level up-线段树-[解题报告]HOJ
2015
04-14

HDU 3954-Level up-线段树-[解题报告]HOJ

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.
I'll play a trick on you

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)

转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents           by—cxlove

 

HDU 3954 level up

http://acm.hdu.edu.cn/showproblem.php?pid=3954

HH的神题,想当初阿里巴巴这比赛是第一次参加的网上的比赛,还是组队的。结果被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夺省赛金牌的队员;
……

不仅仅因为HH取得的成绩,他的精神感染了我,从零基础成为一名在ACM界赫赫有名的大牛。

言归正传,回到题目,区间更新,获得一定的经验可以升级,而每次获得的经验是和等级有关的,这是个难点。

区间lazy是必然的,否则必然TLE。而每次的lazy和以前不一样,由于之后的经验和等级有关,之前lazy的部分可能会导致升级,那之后的就不能按原来的lazy了。

只需要计算区间里的最大等级,经验,以及距离升级需要最小的经验基数(而不是经验总量,每次获得的经验是基数乘以等级的)。

 

/*
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;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acm_cxlove/article/details/7548087


  1. [email protected]

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