频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
hdu 3954 Level up (线段树)
2013-08-17 13:48:49           
收藏   我要投稿

HH大神的神题。只能一直膜拜。。。

从线段树起步都是从他的博客里一点一滴的学的。

风格也是仿照他的来的。

然后说题目吧。

题目意思:会有很多波怪兽袭击,然后也有N个英雄。没来一波怪兽就派 编号是 L-R 的英雄去迎敌。

每个英雄都会获得一定的经验(既是   等级 *  每波的经验基数 E) 。最后Q操作就是问你  L-R 段中哪一个英雄的经验最高,并输出最高值。

 


开始的时候我有点混淆题目。如果他当时还获得的经验足够他升好几级的话,那么当他拿到经验之后,会马上升级,然后升一级以后自己的等级改变了。

把他获得的余下的经验再按新的等级来计算。那么就是雪球越滚越大。然后问了 最小公倍数  学长~~~嚯嚯

 


自己写的时候,是直接把LAZY (cov 数组)  往下推。然后自己意识到这样的lazy不能直接叠加   因为多次操作之后他的等级就会变。

之前的标记就没用了。  那我又想。那每来一个 cov  我就把之前的  cov往下推。  但是显然  这就如单点更新了。

 


通过上一段话,应该能明白代码中的  dis 变量作何用处了

 


dis 是指区间中 那个需求最少经验就可以的英雄  所需要的经验基数。   换句话说   如果这个人都还不能升级的话   那么这个区间内就不会有人能升级了。

那么就可以直接加上  cov  。

如果区间内那个人可以升级。以为这这段区间的某一个人的  lev会发生改变   此时我们就要把这个cov  一直往下推。找到那个变了的人。然后再更新区间。

 

#include <iostream>
#include <cstdio>
#include <algorithm>
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e
#define maxn 10005
using namespace std;

int exp[maxn<<2],lev[maxn<<2];//区间最大经验   区间最大等级
int cov[maxn<<2],dis[maxn<<2];//lazy 标记数组  dis 如上
int ned[15]={0};
int K;

void pushup(int num)
{
    exp[num]=max(exp[num<<1],exp[num<<1|1]);
    lev[num]=max(lev[num<<1],lev[num<<1|1]);
    dis[num]=min(dis[num<<1],dis[num<<1|1]);
}
int getlev(int ex)//找到经验对应的等级
{
    if(ex>=ned[K-1])return K;
    for(int i=1;i<=K;i++)
    {
        if(ex<ned[i])return i;
    }
}
void pushdown(int num)
{
    if(cov[num])
    {
        cov[num<<1|1]+=cov[num];
        cov[num<<1]+=cov[num];

        exp[num<<1]+=(cov[num]*lev[num<<1]);
        exp[num<<1|1]+=(cov[num]*lev[num<<1|1]);

        dis[num<<1]-=cov[num];
        dis[num<<1|1]-=cov[num];

        cov[num]=0;
    }
}
void build(int num,int s,int e)
{
    exp[num]=0;
    lev[num]=1;
    cov[num]=0;
    dis[num]=ned[1];
    if(s==e)return;
    int mid=(s+e)>>1;
    build(lson);
    build(rson);
}
void update(int num,int s,int e,int l,int r,int val)
{
    int mid=(s+e)>>1;
    if(s==e)
    {
        exp[num]+=lev[num]*val;
        lev[num]=getlev(exp[num]);
        dis[num]=(ned[lev[num]]-exp[num])/(lev[num])+((ned[lev[num]]-exp[num])%(lev[num])!=0);
        return ;
    }
    if(l<=s && r>=e)
    {
        if(val<dis[num])
        {
            exp[num]+=lev[num]*val;
            dis[num]-=val;
            cov[num]+=val;
            return ;
        }
        else
        {
            pushdown(num);
            update(lson,s,mid,val);
            update(rson,mid+1,e,val);
            pushup(num);
            return ;
        }
    }
    pushdown(num);

    if(l<=mid)update(lson,l,r,val);
    if(r>mid)update(rson,l,r,val);
    pushup(num);
}

int query(int num,int s,int e,int l,int r)
{
    if(s>=l && e<=r)
    {
        return exp[num];
    }
    pushdown(num);
    int mid=(s+e)>>1;
    if(r<=mid)return query(lson,l,r);
    else if(l>mid)return query(rson,l,r);
    else return max(query(lson,l,mid),query(rson,mid+1,r));
}
int main()
{
    int T,CASE=1;

    scanf("%d",&T);
    while(T--)
    {
        printf("Case %d:\n",CASE++);
        int n,qw;
        scanf("%d%d%d",&n,&K,&qw);

        for(int i=1;i<K;i++)
        {
            scanf("%d",&ned[i]);
        }
        ned[K]=1<<30;
        build(1,1,n);
        while(qw--)
        {
            char tope[5];
            scanf("%s",tope);
            if(tope[0]=='W')
            {
                int a,b,c;
                scanf("%d%d%d",&a,&b,&c);
                update(1,1,n,a,b,c);
            }
            else
            {
                int a,b;
                scanf("%d%d",&a,&b);
                printf("%d\n",query(1,1,n,a,b));
            }
        }
        puts("");
    }
    return 0;
}

/*
5
5 5 999
2 10 15 16
W 1 3 1
W 1 2 1
Q 1 1
*/

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 线段
上一篇:POJ 2114 Boatherds[Tree,点分治]
下一篇:HDU 4679 Terrorist’s destroy (树形DP)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站