题解：P11289 【MX-S6-T1】「KDOI-11」打印

考虑对每个打印机记录下它会在什么时候开始变得空闲。那么，就需要做到：

• 修改某个打印机的空闲时间。
• 查找编号最小的空闲时间 \le x 的打印机的编号，如果没有就查找空闲时间最早的那个打印机编号。

直接线段树二分即可解决。

赛时代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
using pii=pair<int,int>;
using piii=pair<pii,int>;
//文件：下发命令的时刻；打印时间；编号 
//只需要支持：单点修改、查询编号最小的小于等于 x（若无，则最小）的数的位置 
//segtree 即可 
vector<int>pri[N];
piii fi[N];
int n,m;
struct segt{
    struct node{
        int l,r,mn;
    }a[N<<2];
    #define lc(p) ((p)<<1)
    #define rc(p) (((p)<<1)|1)
    void build(int p,int l,int r){
        a[p].l=l,a[p].r=r;
        if(l==r)return;
        int mid=(l+r)>>1;
        build(lc(p),l,mid);
        build(rc(p),mid+1,r);
    }
    void ch(int p,int chp,int x){
        int l=a[p].l,r=a[p].r;
        if(chp<l||r<chp)return;
        if(l==r){
            a[p].mn=x;
            return;
        }
        ch(lc(p),chp,x);
        ch(rc(p),chp,x);
        a[p].mn=min(a[lc(p)].mn,a[rc(p)].mn);
    }
    pii query(int p,int x){
        int l=a[p].l,r=a[p].r;
        if(l==r)return {l,a[p].mn};
        if(max(a[lc(p)].mn,x)<=max(a[rc(p)].mn,x))return query(lc(p),x);
        return query(rc(p),x);
    }
}st;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int s,t;cin>>s>>t;
        fi[i]={{t,s},i};
    }
    sort(fi+1,fi+1+n);
    st.build(1,1,m);
    for(int i=1;i<=n;i++){
        auto tmp=fi[i];
        int s=tmp.first.second,t=tmp.first.first,x=tmp.second;
        auto tmp1=st.query(1,t);
        int xx=tmp1.first,num=tmp1.second;
        pri[xx].emplace_back(x);
        num=max(num,t);
        st.ch(1,xx,num+s);
    }
    for(int i=1;i<=m;i++){
        sort(pri[i].begin(),pri[i].end());
        cout<<pri[i].size();
        for(int x:pri[i])cout<<" "<<x;
        cout<<"\n";
    }
    return 0;
}