HDU 2871 Memory Control（线段树区间合并+各种综合运用）【好题】

古城微笑少年丶 2022-06-11 08:07 144阅读 0赞

Memory units are numbered from 1 up to N.  
A sequence of memory units is called a memory block.  
The memory control system we consider now has four kinds of operations:  
1. Reset Reset all memory units free.  
2. New x Allocate a memory block consisted of x continuous free memory units with the least start number  
3. Free x Release the memory block which includes unit x  
4. Get x Return the start number of the xth memory block(Note that we count the memory blocks allocated from left to right)  
Where 1<=x<=N.You are request to find out the output for M operations.

Input

Input contains multiple cases.  
Each test case starts with two integer N,M(1<=N,M<=50000) ,indicating that there are N units of memory and M operations.  
Follow by M lines,each line contains one operation as describe above.

Output

For each “Reset” operation, output “Reset Now”.  
For each “New” operation, if it’s possible to allocate a memory block,  
output “New at A”,where Ais the least start number,otherwise output “Reject New”.  
For each “Free” operation, if it’s possible to find a memory block occupy unit x,  
output “Free from A to B”,where A and B refer to the start and end number of the memory block,otherwise output “Reject Free”.  
For each “Get” operation, if it’s possible to find the xth memory blocks,  
output “Get at A”,where A is its start number,otherwise output “Reject Get”.  
Output one blank line after each test case.

Sample Input

6 10
    New 2
    New 5
    New 2
    New 2
    Free 3
    Get 1
    Get 2
    Get 3
    Free 3
    Reset

Sample Output

New at 1
    Reject New
    New at 3
    New at 5 
    Free from 3 to 4
    Get at 1
    Get at 5
    Reject Get
    Reject Free
    Reset Now

题解：

这题我没看题解居然做出来了。。花了一天，不过是压线做出来的，花了900ms，虽然是压线但做出来了还是很高兴的，后来看了题解的做法是590ms

题意：

给1-n的内存，m种操作

操作New x，是分配一片连续的内存，位置要求最左，如果不能就输出一句话

操作Free x，看单元x有没有被覆盖，没有就输出一句话，有就输出覆盖区间的最左端点

操作Get x，从左到右数被覆盖的第x个区间，如果没有输出一句话

操作Reset，清空所有内存

这题和Hotel及其相似，感觉是它的加强版，附上之前做那题的链接[点击打开链接][Link 1]

我的做法：

这题的New操作几乎和hotel一模一样，Free我也很快就想出来了，就是当操作为Get的时候我写了好久，后来用二分+树状数组求来求那个合适的点求出来了

ps：

我的线段树部分代码和hotel几乎一模一样，稍做了修改来当为Free时的区间最左端的点，这个部分我就不做过多的解释了，详细看hotel

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    using namespace std;
    struct node
    {
        int l,r;
        int lsm,rsm,maxx;//从左，右数最大连续空余区间，和区间内最大连续空余区间
        int tag;//清除内存为1，覆盖为0，初始-1
        int left,length;//这个是我稍作的修改，当前点如果被区间覆盖，left代表被覆盖的最左端点，length为该区间长度
        int len()//求区间长度
        {
            return r-l+1;
        }
    }t[50005*4];
    int ch;//这里我想出来的有点笨拙的办法，用来存求出来的区间长度的，后面会用
    void Build(int l,int r,int k)
    {
        t[k].l=l;
        t[k].r=r;
        t[k].tag=-1;
        t[k].left=t[k].length=-1;
        t[k].lsm=t[k].rsm=t[k].maxx=r-l+1;//初始化
        if(l==r)
            return;
        int mid=(l+r)/2;
        Build(l,mid,lson);
        Build(mid+1,r,rson);
    }
    void pushup(int k)//区间合并
    {
        t[k].lsm=t[lson].lsm;
        t[k].rsm=t[rson].rsm;
        t[k].maxx=max(max(t[lson].maxx,t[rson].maxx),t[lson].rsm+t[rson].lsm);//求左右子区间，中间区间中最长连续区间中的最大值
        if(t[k].lsm==t[lson].len())//如果左子区间是满的，加上右子区间的左连续长度
            t[k].lsm+=t[rson].lsm;
        if(t[k].rsm==t[rson].len())//同理
            t[k].rsm+=t[lson].rsm;
    }
    void pushdown(int k)//标记下推
    {
        if(t[k].l==t[k].r)
            return;
        if(t[k].tag!=-1)
        {
            t[lson].maxx=t[lson].rsm=t[lson].lsm=t[k].tag*(t[lson].len());//更新子区间
            t[rson].maxx=t[rson].rsm=t[rson].lsm=t[k].tag*(t[rson].len());
            t[lson].tag=t[rson].tag=t[k].tag;
            t[lson].left=t[rson].left=t[k].left;//这里也要更新下推
            t[lson].length=t[rson].length=t[k].length;
            t[k].tag=-1;
        }
    }
    void update(int l,int r,int k,int d,int pos,int len)//l，r为更新区间，d为更新性质，pos为覆盖区间的最左端点，len为覆盖区间长度
    {
        if(t[k].l==l&&t[k].r==r)
        {
            t[k].tag=d;
            t[k].length=len;
            t[k].left=pos;
            t[k].maxx=t[k].rsm=t[k].lsm=d*(t[k].len());//更新一波
            return;
        }
        pushdown(k);//下推标记
        int mid=M;
        if(r<=mid)
            update(l,r,lson,d,pos,len);
        else if(l>mid)
            update(l,r,rson,d,pos,len);
        else
        {
            update(l,mid,lson,d,pos,len);
            update(mid+1,r,rson,d,pos,len);
        }
        pushup(k);//区间合并
    }
    int query(int len,int l,int r,int k)//这里的询问和hotel一样，找最左边的适合的连续区间的左端点
    {
        if(l==r)
            return l;
        pushdown(k);
        int mid=(l+r)/2;
        if(t[lson].maxx>=len)//如果左区间空余区间够在左边找
            return query(len,l,mid,lson);
        else if(t[lson].rsm+t[rson].lsm>=len)//中间如果够的话直接返回端点
            return mid-t[lson].rsm+1;
        else
            return query(len,mid+1,r,rson);//否则在右边找
    }
    int find(int pos,int k)//求pos位置的信息，求该点覆盖的最左端点，顺便用ch求了区间长度，如果没被覆盖会返回-1
    {
        if(t[k].l==t[k].r)
        {
            ch=t[k].length;
            return t[k].left;
        }
        pushdown(k);
        int mid=M;
        if(pos<=mid)
            return find(pos,lson);
        return find(pos,rson);
    }
    int sum[50005];//树状数组
    int lowbit(int x)
    {
        return x&(-x);
    }
    void up(int x,int v)//树状数组日常更新
    {
        while(x<=50000)
        {
            sum[x]+=v;
            x+=lowbit(x);
        }
    }
    int qu(int x)//树状树状日常询问
    {
        int s=0;
        while(x>0)
        {
            s+=sum[x];
            x-=lowbit(x);
        }
        return s;
    }
    int bin(int x)二分求第x个区间
    {
        int l=1,r=50000,mid,t1;
        while(l<r)
        {
            mid=(l+r)/2;
            t1=qu(mid);
            if(t1<x)
            {
                l=mid+1;
            }
            else
            {
                r=mid;
            }
        }
        return l;
    }
    int main()
    {
        char s[10];
        int n,i,j,k,m,x,pos,ans;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            Build(1,n,1);
            ans=0;//当前覆盖的区间个数
            memset(sum,0,sizeof(sum));
            for(i=0;i<m;i++)
            {
                scanf("%s",s);
                if(s[0]=='N')
                {
                    scanf("%d",&x);
                    if(t[1].maxx<x)//如果数字大于最大区间的连续空余长度
                    {
                        printf("Reject New\n");
                        continue;
                    }
                    else
                    {
                        pos=query(x,1,n,1);
                        printf("New at %d\n",pos);
                        update(pos,pos+x-1,1,0,pos,x);//更新一波
                        up(pos,1);树状数组这里也要更新，相当于在左端点处赋值为1
                        ans++;
                    }
                }
                else if(s[0]=='F')
                {
                    scanf("%d",&x);
                    pos=find(x,1);//用单点询问找x点出情况
                    if(pos==-1)//如果没被覆盖
                    {
                        printf("Reject Free\n");
                        continue;
                    }
                    else
                    {
                        printf("Free from %d to %d\n",pos,pos+ch-1);//ch的作用体现出来了
                        update(pos,pos+ch-1,1,1,-1,-1);//后面两个参数很重要，为-1说明没被覆盖
                        up(pos,-1);//相当于在该区间左端点位置赋值为0
                        ans--;
                    }
                }
                else if(s[0]=='G')
                {
                    scanf("%d",&x);
                    if(x>ans)
                    {
                        printf("Reject Get\n");
                        continue;
                    }
                    else
                    {
                        pos=bin(x);//二分找第x个区间
                        printf("Get at %d\n",pos);
                    }
                }
                else
                {
                    update(1,n,1,1,-1,-1);//清空所有内存。。一开始写成build了无限TLE
                    ans=0;
                    memset(sum,0,sizeof(sum));//清空树状数组值
                    printf("Reset Now\n");
                }
    
    
            }
            printf("\n");
        }
        return 0;
    }

然后接下来是看着博客的题解写的，就没用树状树状求get的位置，用的是stl里的vector和自带的二分查找函数。。果然快了很多，590ms，学到了

这里补充一下关于vector函数的知识：

iterator lower\_bound( const key\_type &key ): 返回一个迭代器，指向键值>= key的第一个元素。  
iterator upper\_bound( const key\_type &key ):返回一个迭代器，指向键值> key的第一个元素。

线段树部分和上面的几乎一模一样就不打注释了，就是去掉了我自己用的那个笨拙方法部分

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    using namespace std;
    struct node
    {
        int l,r;
        int lsm,rsm,maxx;
        int tag;
        int len()
        {
            return r-l+1;
        }
    }t[50005*4];
    void Build(int l,int r,int k)
    {
        t[k].l=l;
        t[k].r=r;
        t[k].tag=-1;
        t[k].lsm=t[k].rsm=t[k].maxx=r-l+1;
        if(l==r)
            return;
        int mid=(l+r)/2;
        Build(l,mid,lson);
        Build(mid+1,r,rson);
    }
    void pushup(int k)
    {
        t[k].lsm=t[lson].lsm;
        t[k].rsm=t[rson].rsm;
        t[k].maxx=max(max(t[lson].maxx,t[rson].maxx),t[lson].rsm+t[rson].lsm);
        if(t[k].lsm==t[lson].len())
            t[k].lsm+=t[rson].lsm;
        if(t[k].rsm==t[rson].len())
            t[k].rsm+=t[lson].rsm;
    }
    void pushdown(int k)
    {
        if(t[k].tag!=-1)
        {
            t[lson].maxx=t[lson].rsm=t[lson].lsm=t[k].tag*(t[lson].len());
            t[rson].maxx=t[rson].rsm=t[rson].lsm=t[k].tag*(t[rson].len());
            t[lson].tag=t[rson].tag=t[k].tag;
            t[k].tag=-1;
        }
    }
    void update(int l,int r,int k,int d)
    {
        if(t[k].l==l&&t[k].r==r)
        {
            t[k].tag=d;
            t[k].maxx=t[k].rsm=t[k].lsm=d*(t[k].len());
            return;
        }
        pushdown(k);
        int mid=M;
        if(r<=mid)
            update(l,r,lson,d);
        else if(l>mid)
            update(l,r,rson,d);
        else
        {
            update(l,mid,lson,d);
            update(mid+1,r,rson,d);
        }
        pushup(k);
    }
    int query(int len,int l,int r,int k)
    {
        if(l==r)
            return l;
        pushdown(k);
        int mid=(l+r)/2;
        if(t[lson].maxx>=len)
            return query(len,l,mid,lson);
        else if(t[lson].rsm+t[rson].lsm>=len)
            return mid-t[lson].rsm+1;
        else
            return query(len,mid+1,r,rson);
    }
    struct edge
    {
        int l,r;
    };
    vector<edge>q;
    int cmp(edge x,edge y)//用于二分查找的函数
    {
        return x.l<y.l;
    }
    vector<edge>::iterator it;//vector的迭代器
    int main()
    {
        char s[10];
        int n,i,j,k,m,x,pos;
        edge now;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            Build(1,n,1);
            q.clear();
            for(i=0;i<m;i++)
            {
                scanf("%s",s);
                if(s[0]=='N')
                {
                    scanf("%d",&x);
                    if(t[1].maxx<x)
                    {
                        printf("Reject New\n");
                        continue;
                    }
                    else
                    {
                        pos=query(x,1,n,1);
                        printf("New at %d\n",pos);
                        update(pos,pos+x-1,1,0);
                        now.l=pos;
                        now.r=pos+x-1;
                        it=upper_bound(q.begin(),q.end(),now,cmp);//先排序，再二分查找第一个大于当前区间左端点
                        q.insert(it,now);在找到的端点前插入当前区间
                    }
                }
                else if(s[0]=='F')
                {
                    scanf("%d",&x);
                    now.l=now.r=x;
                    it=upper_bound(q.begin(),q.end(),now,cmp);//同理找第一个大于x的左端点的区间
                    if(it==q.begin())如果x小于最前面区间的左端点
                    {
                        printf("Reject Free\n");
                        continue;
                    }
                    else
                    {
                        it--;//得到x可能处于的区间
                        if(it->r<now.l)//如果该区间的右端点小于x，就是x没被覆盖
                            printf("Reject Free\n");
                        else
                        {
                            printf("Free from %d to %d\n",it->l,it->r);
                            update(it->l,it->r,1,1);
                            q.erase(it);//记得去掉
                        }
                    }
                }
                else if(s[0]=='G')
                {
                    scanf("%d",&x);
                    if(x>q.size())
                    {
                        printf("Reject Get\n");
                        continue;
                    }
                    else
                    {
                        printf("Get at %d\n",q[x-1].l);//因为已经有序了
                    }
                }
                else
                {
                    update(1,n,1,1);//如果写成build会TLE
                    q.clear();//记得清除
                    printf("Reset Now\n");
                }
    
            }
            printf("\n");
        }
        return 0;
    }

[Link 1]: http://blog.csdn.net/qq_37497322/article/details/74294215