HDU 2871 Memory Control(线段树:区间合并)
http://acm.hdu.edu.cn/showproblem.php?pid=2871
分析:
首先分析题目中能进行的几种操作:
1. Reset: 所有内存单元置0
2. New x:申请一块包含连续x个单元的空闲内存块
3. Freex: 释放包含x号单元的(已被占用)内存块
4. Get x:返回第x个被占用的内存块的起始地址.
根据上面的分析我们知道维护一棵线段树,每个节点应该具有的
信息是:
1. cover[i](根本信息) : 为0或i或-1,为0时表示未被占用,为i时的含义是:对于题目中的第i条New命令,如果申请成功就置所有被申请单元的cover位为i, 为-1时表示儿子节点的cover位不一致
2. sub[i]:表示i节点控制区间的最长连续空闲区间长度,.
3. pre[i]: i节点控制区间的最长前缀连续空闲区间的长度
4. suf[i]:i节点控制区间的最长后缀连续空闲区间的长度
上面4种信息能解决reset和new的问题.下面还有几个需要全局维护的信息,由于命令最多5W条,所以就算cover位的值最多为5W,所以需要维护的信息有:
1. Interval[MAXN]:和sub一样是二元组(x,y)的结构体,Interval[i]包含了第i个New操作所申请到的区间的起始坐标x和终止坐标y.注意这里的第i个并不代表该(x,y)在整个内存中是从左到右的第i个位置.而且这Interval信息就算Update更新了线段树,也不用更改.
这个Interval信息,是在query_sub之后得到区间后更新的.
如果要执行Free x操作,先查询到x单元的cover位的值,如果非0则就可以在interval中找到区间[L,R],然后用update把区间置0即可.
如果要执行Get x操作,只需要用一个hash数组标记,遍历一遍线段树找到第x个出现的cover位即可,然后在interval中查询其实坐标x.
线段树的具体实现:
1. build(i,l,r): 建立一棵以i节点为根的线段树.
如果l==r,那么更新cover,sub,pre,suf信息
否则递归建立左右子树,然后PushUp操作.
2. PushDown(i,l,r):如果cover[i]!=-1,将cover位传递下去,更新子节点的suf,sub,pre信息.
3. PushUp(i,l,r):有子树信息更新父节点的cover,sub,suf,pre信息.
4. update(ql,qr,v,i,l,r):将[ql,qr]与[l,r]重叠部分区间cover位置v值.
如果ql<=l&&r<=qr,那么直接置cover,更新sub,suf,pre.否则先PushDown,然后递归update左右子树,最后PushUp.
5. query_free(x,i,l,r):找到x单元所在的内存块.首先x肯定在[l,r]中.
如果当前cover[i]!=-1,那么直接返回cover位(为0,则Reject free).否则PushDown后递归查询左右子树.
6. query_get(x,i,l,r):找到从左到右第x块被占用的内存块的cover位编号记录在cnt_num中.
首先每次query_get前都要讲hash置false,然后用cnt记录当前已经找过了多少块被占用的内存块.用cnt_num记录那个第x块被占用的内存快的cover位.
如果cnt>=x了,那么直接返回即可.
如果当前cover!=-1,那么直接处理返回不递归,如果cover==-1,还需要递归查询子树.
7. query(ql,qr,x,i,l,r):返回[ql,qr]与[l,r]公共部分的连续空闲区间大小>=x的那个起始地址最小的区间的起始坐标
首先如果sub[i]<x,直接返回-1.
注意:如果l==r的话也要立刻return否则无限递归.
PushDown操作之后,
如果sub[i*2]>=x,那么直接返回qeury(ql,qr,lson).
否则如果L2=(左儿子的最长后缀起始坐标x, 右儿子的最长前缀终点坐标y),L2区间的长度>=x,那么也直接返回L2.
最后只能(也必定)直接返回query(ql,qr,rson).
注意:使用new的时候,先query这里查询返回的是区间[L,R],且该区间>=x,所以我们之后在main中还需要update更新区间[L,L+x-1]
由于在query函数中没有加上l==r时返回,导致在New 1操作的时候会无限递归,一致RTE(存取错误)了半天.
AC代码:359ms
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=50000+1000;
#define lson i*2,l,m
#define rson i*2+1,m+1,r
#define root 1,1,n
struct Interval
{
int x,y;
}interval[MAXN];
int cover[MAXN*4],sub[MAXN*4],suf[MAXN*4],pre[MAXN*4];
bool hash[MAXN];
int cnt;//初值为0
int cnt_num;
int all;//记录当前内存中一共有多少块内存块
void PushDown(int i,int l,int r)
{
int m=(l+r)/2;
if(cover[i]!=-1)
{
cover[i*2]=cover[i*2+1]=cover[i];
sub[i*2]=suf[i*2]=pre[i*2]= (cover[i]?0:m-l+1);
sub[i*2+1]=suf[i*2+1]=pre[i*2+1]= (cover[i]?0:r-m);
}
}
void PushUp(int i,int l,int r)
{
int m=(l+r)/2;
//cover
if(cover[i*2]==-1 || cover[i*2+1]==-1)
cover[i]=-1;
else if(cover[i*2] != cover[i*2+1])
cover[i]=-1;
else
cover[i]=cover[i*2];
//sub
sub[i]=max(suf[i*2]+pre[i*2+1],max(sub[i*2],sub[i*2+1]));
//pre
pre[i]=pre[i*2];
if(pre[i]==m-l+1)pre[i]+=pre[i*2+1];
//suf
suf[i]=suf[i*2+1];
if(suf[i]==r-m)suf[i] += suf[i*2];
}
void build(int i,int l,int r)
{
if(l==r)
{
cover[i]=0;
sub[i]=suf[i]=pre[i]=1;
return ;
}
int m=(l+r)/2;
build(lson);
build(rson);
PushUp(i,l,r);
}
void update(int ql,int qr,int v,int i,int l,int r)
{
if(ql<=l&&r<=qr)
{
cover[i]=v;
suf[i]=sub[i]=pre[i]= (v?0:r-l+1);
return ;
}
PushDown(i,l,r);
int m=(l+r)/2;
if(ql<=m) update(ql,qr,v,lson);
if(m<qr) update(ql,qr,v,rson);
PushUp(i,l,r);
}
int query_free(int x,int i,int l,int r)//x肯定被区间[l,r]包含
{
if(cover[i]!=-1)
return cover[i];
PushDown(i,l,r);
int m=(l+r)/2;
if(x<=m) return query_free(x,lson);
return query_free(x,rson);
}
void query_get(int x,int i,int l,int r)
{
if(cnt>=x)
return ;
if(cover[i]!=-1)
{
if(cover[i]>0)
{
if(hash[cover[i]]==false)
{
hash[cover[i]]=true;
cnt++;
}
if(cnt==x) cnt_num = cover[i];
}
return ;
}
int m =(l+r)/2;
query_get(x,lson);
if(cnt>=x)
return ;
query_get(x,rson);
}
int query(int ql,int qr,int x,int i,int l,int r)//返回满足需求的区间左端点坐标
{
if(sub[i]<x)
return -1;
if(l==r)//这句话不加的话,就将在New 1的时候无限递归,RTE(存取错误)
return l;
PushDown(i,l,r);
int m=(r+l)/2;
if(sub[i*2]>=x) return query(ql,qr,x,lson);
else
{
int len_l= min(suf[i*2],m-ql+1);//左子树的后缀在[ql,qr]内的公共最长长度
int len_r= min(pre[i*2+1],qr-m);//右子树的前缀在[ql,qr]内的公共最长长度
if(len_l+len_r >=x)
return m-len_l+1;
}
return query(ql,qr,x,rson);
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)==2&&n&&m)
{
all=0;//当前内存一共0块内存被占用
build(root);
for(int i=1;i<=m;i++)
{
char str[10];
int x;
scanf("%s",str);
if(str[0]=='R')
{
all=0;//被占用的块清0
update(1,n,0,root);
printf("Reset Now\n");
}
else if(str[0]=='N')
{
scanf("%d",&x);
if(sub[1]<x)
printf("Reject New\n");
else
{
int L=query(1,n,x,root);
printf("New at %d\n",L);
update(L,L+x-1,i,root);
interval[i].x=L;
interval[i].y=L+x-1;
all++;//被占用内存多了1块
}
}
else if(str[0]=='F')
{
scanf("%d",&x);
if(x>n||x<=0)
{
printf("Reject Free\n");
continue;
}
int id=query_free(x,root);
if(id==0)
printf("Reject Free\n");
else
{
int ql=interval[id].x,qr=interval[id].y;
printf("Free from %d to %d\n",ql,qr);
update(ql,qr,0,root);
all--;
}
}
else if(str[0]=='G')
{
scanf("%d",&x);
if(x>all)
printf("Reject Get\n");
else
{
memset(hash,false,sizeof(hash));
cnt=0;
cnt_num=0;
query_get(x,root);
printf("Get at %d\n",interval[cnt_num].x);
}
}
}
printf("\n");
}
return 0;
}