题解：P5763 [NOI1999] 内存分配

· · 题解

这是一篇时间复杂度 O(k\log k)，空间复杂度 O(k) 的做法，应该是目前的理论最优解。在本题时空限制下应该可以跑过 k=10^6。（此处 k 指行数）

将每个空闲单元视为 1，被占用的单元视为 0，那么我们就得到了一些 01 连续段。考虑用平衡树维护。（经过摊还分析可知这是对的）。我此处只维护了连续 1 段。

我们需要用平衡树实现：

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

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

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

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

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

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

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

以下是我用 fhq_treap 的实现：

#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);
    }
}