题解：P5763 [NOI1999] 内存分配

这是一篇时间复杂度

O(k\log k)

，空间复杂度

O(k)

的做法，应该是目前的理论最优解。在本题时空限制下应该可以跑过

k=10^6

。（此处

k

指行数）

将每个空闲单元视为

1

，被占用的单元视为

0

，那么我们就得到了一些

01

连续段。考虑用平衡树维护。（经过摊还分析可知这是对的）。我此处只维护了连续

1

段。

我们需要用平衡树实现：

找到第一个长度 $\ge m$ 的连续 $1$ 段；
将一个区间改为 $0$ 或 $1$ 。

寻找过程可以维护最长段，采用平衡树上二分。

修改可以简单地增删节点维护。

对于在队列中的单元直接开一个队列维护。

对于停止占用的节点开一个按结束时间的小根堆维护。

具体不太好实现，平衡树可以节点回收，这样可能会好写一点。

另外注意特判一个时间点有多个进程同时结束。

以下是我用 fhq_treap 的实现：

CPP

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<chrono>
#include<random>
#include<queue>
using namespace std;
char *p1,*p2,buf[10010];
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,10000,stdin),p1==p2)?EOF:*p1++)
int read(){
	int x=0;
	char c=gc();
    while(c<48)c=gc();
	while(47<c)x=(x<<3)+(x<<1)+(c&15),c=gc();
	return x;
}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
struct node{
	int l,r,L,R,mx,rd;
}t[10010];
struct SEG{
	int t,l,r;
	SEG(int tt=0,int ll=0,int rr=0){
		t=tt;
		l=ll;
		r=rr;
	}
	bool operator<(SEG _)const{
		return _.t<t||_.t==t&&_.l<l;
	}
};
priority_queue<SEG>q1;
pair<int,int>q[10010];
int new_node(int l,int r);
int tot,stk[10010],top,rt=new_node(0,read()-1),hh=1,tt,ans;
int new_node(int l,int r){
	if(top){
		int x=stk[top--];
		t[x].mx=(t[x].R=r)-(t[x].L=l)+1;
		return x;
	}
	t[++tot].rd=rnd();
	t[tot].mx=(t[tot].R=r)-(t[tot].L=l)+1;
	return tot;
}
void update(int now){
	t[now].mx=max(t[now].R-t[now].L+1,max(t[t[now].l].mx,t[t[now].r].mx));
}
void split(int now,int k,int&x,int&y){
	if(!now)x=y=0;
	else{
		if(t[now].L<=k){
			x=now;
			split(t[now].r,k,t[now].r,y);
		}else{
			y=now;
			split(t[now].l,k,x,t[now].l);
		}
		update(now);
	}
}
int merge(int x,int y){
	if(!x||!y)return x|y;
	if(t[x].rd<t[y].rd){
		t[x].r=merge(t[x].r,y);
		update(x);
		return x;
	}
	t[y].l=merge(x,t[y].l);
	update(y);
	return y;
}
int queryl(int now){
	while(t[now].l)now=t[now].l;
	return now;
}
int queryr(int now){
	while(t[now].r)now=t[now].r;
	return now;
}
int query(int now,int k){
	if(t[t[now].l].mx>=k)return query(t[now].l,k);
	if(t[now].R-t[now].L+1>=k)return now;
	return query(t[now].r,k);
}
void add(int m,int p){
	int x,y,k=query(rt,m);
	split(rt,t[k].L,x,y);
	split(x,t[k].L-1,x,k);
	q1.emplace(p,t[k].L,t[k].L+m-1);
	if(t[k].mx==m){
		stk[++top]=k;
		rt=merge(x,y);
	}else{
		t[k].L+=m;
		t[k].mx=t[k].R-t[k].L+1;
		rt=merge(merge(x,k),y);
	}
}
void del(SEG seg,unsigned char fl){
	int L=seg.l,R=seg.r,x,y,l,r;
	ans=max(ans,seg.t);
	split(rt,L,x,y);
	l=queryr(x);
	r=queryl(y);
	if(l&&t[l].R==L-1){
		L=t[l].L;
		split(x,L-1,x,l);
		stk[++top]=l;
	}
	if(r&&t[r].L==R+1){
		R=t[r].R;
		split(y,R,r,y);
		stk[++top]=r;
	}
	rt=merge(merge(x,new_node(L,R)),y);
	if(fl)while(hh<=tt&&t[rt].mx>=q[hh].first){
		add(q[hh].first,q[hh].second+seg.t);
		++hh;
	}
}
int main(){
	int t,m,p;
	SEG seg;
	while(1){
		t=read();
		m=read();
		p=read();
		if(!t&&!m&&!p){
			while(!q1.empty()){
				seg=q1.top();
				q1.pop();
				del(seg,q1.empty()||!q1.empty()&&q1.top().t!=seg.t);
			}
			printf("%d\n%d",ans,tt);
			return 0;
		}
		while(!q1.empty()&&q1.top().t<=t){
			seg=q1.top();
			q1.pop();
			del(seg,q1.empty()||!q1.empty()&&q1.top().t!=seg.t);
		}
		if(::t[rt].mx>=m)add(m,p+t);
		else q[++tt]=make_pair(m,p);
	}
}

题解：P5763 [NOI1999] 内存分配

文章操作

相关推荐

评论

题解：P5763 [NOI1999] 内存分配