欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU 2871 Memory Control (线段树区间合并)

程序员文章站 2022-06-02 13:39:13
...

题意:

现在有一个内存条,有四操作,第一种是用掉一段内存,从左向右找第一个能插的地方插,并输出位置,没有就输出“Reject New”,第二种是清空某个位置所处的内存段,并输出左右边缘,没有就输出“Reject Free”,第三种是清空全部内存,第四种是得到第k块内存的头在哪里

思路:

很麻烦的区间合并,看见的时候一时间只有相当麻烦的思路,就是暴力地在线段树上保存每一段的数据(包括左右节点和个数),但是很明显这样是有问题的,首先在向上更新的时候,会将左右节点合并掉,并且向上容易,但是在查找的时候也很那按将合并好的节点拆开

扯远了,我只能找博客找题解,然而大部分题解对于方法的介绍都很少,甚至有错误的地方,经过仔细研读了http://blog.csdn.net/libin56842/article/details/16872927这个博客的代码,我终于理解出一种巧妙的方法,原博客介绍的很少,下面我来仔细介绍下

首先,我们对于每段数据,可以只记录头节点,这样就能非常方便的记录个数了,因为我们只要在线段树上不断求和,就能保证这颗线段树统计的数据个数是正确的(即使是1的数据段也是可以的),并且在查找头位置的时候也十分方便,这就对应了Get操作
通过基础的区间合并的操作(也就是lsum,rsum,msum)我们就能解决new的问题,而reset我们能非常方便地通过lazy解决掉,这样我们只剩下free操作,我们如果维护一个s和e来维护某段所处的内存段最左和最右,那么我们只要把头节点求出来,就能直接得到开始和结束的位置

错误及反思:

这题百度到的题解有的是错的,因为这个题数据不行,很多人用vector暴力地保存区间,这样虽然让get操作很方便,但是其实维护复杂度是O(n)的(因为加入是insert),如果数据有是这样的,一开始内存是1e5个1,然后不断的删第一个,再加入一个1,这样用vector的复杂度就会爆掉了,可是这个题很明显没有这种数据,所以用vector能卡过去,最后说一下,记得多组和防PE

代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lrt rt<<1
#define rrt rt<<1|1
const int N = 50010;
int lsum[N<<2],rsum[N<<2],msum[N<<2],lazy[N<<2],cnt[N<<2],cover[N<<2],s[N<<2],e[N<<2];
int n,k,ta;
//lsum rsum msum lazy都是正常区间合并的操作
//cnt表示开头的数量
//cover 类似lazy
//s e表示每段的开头和结尾
void pushdown(int l,int r,int rt)
{
    if(lazy[rt]!=-1)
    {
        int m=(l+r)/2;
        lazy[lrt]=lazy[rrt]=lazy[rt];
        msum[lrt]=lsum[lrt]=rsum[lrt]=(m-l+1)*lazy[rt];
        msum[rrt]=lsum[rrt]=rsum[rrt]=(r-m)*lazy[rt];
        s[lrt]=s[rrt]=s[rt];
        e[lrt]=e[rrt]=e[rt];
        lazy[rt]= -1;
    }
}
void pushup(int l,int r,int rt)
{
    int m=(l+r)/2;
    lsum[rt]=lsum[lrt];
    rsum[rt]=rsum[rrt];
    if(lsum[rt]==m-l+1)
        lsum[rt]+=lsum[rrt];
    if(rsum[rt]==r-m)
        rsum[rt]+=rsum[lrt];
    msum[rt]=max(lsum[rrt]+rsum[lrt],max(msum[lrt],msum[rrt]));
}
void update(int L,int R,int v,int l,int r,int rt)
{
    if(L<=l&&R>=r)
    {
        lazy[rt]=v;
        lsum[rt]=rsum[rt]=msum[rt]=(r-l+1)*v;
        if(v) s[rt]=e[rt]=-1;
        else
        {
            s[rt]=L;
            e[rt]=R;
        }
        return ;
    }
    pushdown(l,r,rt);
    int m=(l+r)/2;
    if(L<=m) update(L,R,v,lson);
    if(R>m) update(L,R,v,rson);
    pushup(l,r,rt);
}
void build()
{
    update(1,n,1,1,n,1);
    cnt[1]=0;
    cover[1]=1;
}
int New(int x,int l,int r,int rt)
{
    if(l == r)
        return l;
    int m=(l+r)/2;
    pushdown(l,r,rt);
    if(msum[lrt]>=x) return New(x,lson);
    else if(rsum[lrt]+lsum[rrt]>=x)
        return m-rsum[lrt]+1;
    else
        return New(x,rson);
}
int Free(int x,int l,int r,int rt)
{
    if(l == r)
        return rt;
    int m = (l+r)>>1;
    pushdown(l,r,rt);
    if(x<=m) return Free(x,lson);
    else return Free(x,rson);
}
void countup(int rt)
{
    cnt[rt]=cnt[lrt]+cnt[rrt];
}
void countdown(int rt)
{
    if(cover[rt])
    {
        cnt[lrt]=cnt[rrt]=0;
        cover[lrt]=cover[rrt]=1;
        cover[rt]=0;
    }
}
int Get(int x,int l,int r,int rt)
{
    if(l == r)
        return l;
    int m = (l+r)/2;
    countdown(rt);
    if(cnt[lrt]>=x)
        return Get(x,lson);
    else
        return Get(x-cnt[lrt],rson);
}
void cal(int x,int t,int l,int r,int rt)
{
    if(l == r){
        cnt[rt] = t;
        return ;
    }
    int m = (l+r)/2;
    countdown(rt);
    if(x<=m) cal(x,t,lson);
    else cal(x,t,rson);
    countup(rt);
}
int main()
{
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        build();
        while(k--)
        {
            char te[20];
            scanf("%s",te);
            if(te[0]=='N')
            {
                scanf("%d",&ta);
                if(msum[1]<ta)
                    printf("Reject New\n");
                else{
                    int an=New(ta,1,n,1);
                    printf("New at %d\n",an);
                    cal(an,1,1,n,1);
                    update(an,an+ta-1,0,1,n,1);
                }
            }
            else if(te[0]=='F')
            {
                scanf("%d",&ta);
                int an = Free(ta,1,n,1);
                if(s[an]<0)
                    printf("Reject Free\n");
                else{
                    printf("Free from %d to %d\n",s[an],e[an]);
                    cal(s[an],0,1,n,1);
                    update(s[an],e[an],1,1,n,1);
                }
            }
            else if(te[0]=='R')
            {
                build();
                printf("Reset Now\n");
            }
            else
            {
                scanf("%d",&ta);
                if(ta>cnt[1])
                    printf("Reject Get\n");
                else
                    printf("Get at %d\n",Get(ta,1,n,1));
            }
        }
        puts("");//居然卡PE
    }
}
相关标签: 合并