HDU 2871 Memory Control (线段树区间合并)
题意:
现在有一个内存条,有四操作,第一种是用掉一段内存,从左向右找第一个能插的地方插,并输出位置,没有就输出“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
}
}
上一篇: datetable合并成一个
下一篇: Merge 标签与布局优化