题解：P7013 [CERC2013] History course

· · 题解

好困难啊。

显然可以二分答案，首先考虑一个 O(n^2) 做一遍 check 的暴力，其实就是 CF309E。

我们维护每个区间能被放置到的最后位置 las_i，初始时 las_i=n，我们从前往后确定填入的区间。

假设当前填到第 i 位，如果无解的话，那么会有一个 j，[i,j] 内需要填超过 j-i+1 个区间，也就是 las_i 在 [i,j] 范围内的数大于 j-i+1，可以记录一个 cnt 数组，用前缀和做到 O(n) 处理。

然后我们选择填哪个区间，我们考虑最小的 pos，满足 [i,pos] 内有 pos-i+1 个数需要填，这个时候我们必定选择一个 las_i\in[i,pos] 的数，否则下一次就矛盾了。

满足这个限制之后，我们选择一个最小的 r，这样会能够有交的区间会尽可能少，之后对于所有与这个区间相交的区间，把 las_i 更新为 \min(las_i,i+mid) 即可。

::::info[code]

int L[N],R[N];
int las[N],ans[N],flag[N];
int cnt[N];
bool check(int mid){
    for(int i=1;i<=n;i++)las[i]=n,ans[i]=flag[i]=0;
    for(int i=1;i<=n;i++){
        memset(cnt,0,sizeof cnt);
        for(int j=1;j<=n;j++)if(!flag[j])cnt[las[j]]++;
        for(int j=1;j<=n;j++)cnt[j]+=cnt[j-1];
        for(int j=i;j<=n;j++)if(cnt[j]>j-i+1)return false;
        int pos=0,now=0;
        for(pos=i;pos<=n;pos++)if(cnt[pos]==pos-i+1)break;
        for(int j=1;j<=n;j++)if((!flag[j])&&(las[j]<=pos)&&(R[j]<R[now]||!now))now=j;
        flag[ans[i]=now]=1;
        for(int j=1;j<=n;j++)if((L[j]<=R[now])&&(L[now]<=R[j]))chkmin(las[j],i+mid);
    }
    return true;
}
//  O(n^2\log n) 期望得分 0

:::: 贪心的 part 结束，接下来是大家喜闻乐见的 ds 环节。

考虑我们需要维护什么，可以维护一个 cnt 数组，发现每次找 cnt_j=j-i+1 不好做，维护 cnt_i-i 即可，我们需要的 pos 就是 cnt_j-j 最大值的位置。

对于修改操作看上去不好做，但是我们发现我们发现 las_i 只能被修改一次，这个性质就非常牛了，又因为我们每次覆盖的是一个前缀，las_i 是按照 l_i 的大小覆盖的，于是我们把序列按照 l 排序，维护 las_i 被覆盖到的位置即可。

然后我们还需要找到 las_i\le pos 时最小的 r_i，注意到排完序之后 las_i 有单调性，我们在线段树上面二分即可解决。

再加上二分，时间复杂度是 O(n\log^2n) 的，根据包队定理这题没过，我还是太失败了。

好像要特判一下答案为 0 的情况，可能是我实现不太好。

::::info[code]

const int N=5e4+5,inf=1e9+7;
int n,m,T;
int L[N],R[N];
int ans[N];
struct SegmentTree1{
    struct Node{
        int p,mx;
        Node(){p=0,mx=-inf;}
        Node(int _p,int _mx){p=_p,mx=_mx;}
    }tr[N<<2];
    int lazy[N<<2];
    friend Node operator+(Node x,Node y){
        Node sum; 
        sum.mx=max(x.mx,y.mx);
        if(y.mx==sum.mx)sum.p=y.p;
        if(x.mx==sum.mx)sum.p=x.p;
        if(x.mx==y.mx)sum.p=min(x.p,y.p);
        return sum;
    }
    #define mid ((l+r)>>1)
    #define lson u<<1,l,mid
    #define rson u<<1|1,mid+1,r
    void pushup(int u){
        tr[u]=tr[u<<1]+tr[u<<1|1];
    }
    void cover(int u,int v){
        tr[u].mx+=v,lazy[u]+=v;
    }
    void pushdown(int u){
        cover(u<<1  ,lazy[u]);
        cover(u<<1|1,lazy[u]);
        lazy[u]=0;
    }
    void build(int u,int l,int r){
        lazy[u]=0;
        if(l==r)return (void)(tr[u]=Node(l,(l==n)?0:(-l)));
        build(lson),build(rson);
        pushup(u);
    }
    void modify(int u,int l,int r,int x,int y,int v){
        if(x<=l&&r<=y)return cover(u,v);
        pushdown(u);
        if(x<=mid)modify(lson,x,y,v);
        if(y> mid)modify(rson,x,y,v); 
        pushup(u);
    }
    Node query(int u,int l,int r,int x,int y){
        if(x<=l&&r<=y)return tr[u];
        pushdown(u);
        Node res; res.mx=-inf,res.p=0;
        if(x<=mid)res=res+query(lson,x,y);
        if(y> mid)res=res+query(rson,x,y);
        return res; 
    }
}seg1;
int id[N];
int cmp(int x,int y){
    return L[x]<L[y];
}
#define root 1,1,n
struct SegmentTree2{
    struct Node{int rm,ls,lm,lx;}tr[N<<2];
    friend Node operator+(Node a,Node b){
        return (Node){((R[id[a.rm]]>R[id[b.rm]])?b.rm:a.rm),min(a.ls,b.ls),min(a.lm,b.lm),max(a.lx,b.lx)};
    }
    void pushup(int u){
        tr[u]=tr[u<<1]+tr[u<<1|1];
    }
    void build(int u,int l,int r){
        if(l==r)return (void)(tr[u]=(Node){l,n,L[id[l]],n});
        build(lson),build(rson);
        pushup(u);
    }
    void modify(int u,int l,int r,int y,int v){
        if(tr[u].lm>y)return ;
        if(l==r){
            seg1.modify(root,v,n-1,1);
            tr[u].ls=tr[u].lx=v,tr[u].lm=inf;
            return ;
        }
        modify(lson,y,v),modify(rson,y,v);
        pushup(u);
    }
    void del(int u,int l,int r,int p){
        if(l==r){
            seg1.modify(root,min(tr[u].ls,n),n,-1);
            tr[u].lx=0,tr[u].lm=tr[u].ls=inf,tr[u].rm=0;
            return ;
        }
        if(p<=mid)
            del(lson,p);
        else 
            del(rson,p);
        pushup(u);
    }
    int query(int u,int l,int r,int y){
        if(tr[u].lx<=y)return tr[u].rm;
        if(tr[u].ls> y)return 0;
        int ql=query(lson,y),qr=query(rson,y);
        return (R[id[ql]]>R[id[qr]])?qr:ql;
    }
}seg2;
#undef mid 
bool check(int mid){
    R[0]=inf;
    for(int i=1;i<=n;i++)id[i]=i; sort(id+1,id+1+n,cmp);
    seg1.build(root),seg2.build(root);
    for(int i=1;i<=n;i++){
        auto t=seg1.query(root,i,n);
        if(t.mx>1-i)return false;
        int now=seg2.query(root,t.p);
        ans[i]=id[now];
        seg2.del(root,now);
        if(i+mid<n)seg2.modify(root,R[id[now]],i+mid);
    }
    return true;
}
bool CheckZero(){
    for(int i=1;i<=n;i++)id[i]=i; sort(id+1,id+1+n,cmp);
    for(int i=2;i<=n;i++)if(L[id[i]]<=R[id[i-1]])return 0;
    printf("0\n");
    for(int i=1;i<=n;i++)printf("%d %d\n",L[id[i]],R[id[i]]);
    return 1;
}
int main(){
    T=read();
    while(T--){
        n=read();
        for(int i=1;i<=n;i++)L[i]=read(),R[i]=read();
        if(CheckZero())continue;
        int l=1,r=n-1;
        while(l<r){
            int mid=(l+r)>>1;
            if(check(mid))r=mid;
            else l=mid+1;
        }
        assert(check(l));
        printf("%d\n",l);
        for(int i=1;i<=n;i++)printf("%d %d\n",L[ans[i]],R[ans[i]]);
    }
    return 0;
}

::::