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

我的做法是无脑线段树。

• 对于每一个打印机，我们使他们初始的可以使用的时间为零。

• 对于每一次打印操作，我们可以通过线段树快速求出等待时间最少的并且编号最小的点。

• 求出以后我们将这个打印机下一次可以使用的时间更新。

• 因为线段树维护的是下一次使用的时间节点，所以在查询时我们需要判断如果他的下一次使用节点小于等于当前时间那么我们默认他为零，否则减去当前时间再进行比较。

具体实现见代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read() {
    int x=0, w=1; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1; ch=getchar();}
    while(isdigit(ch)) {x=x*10+(ch-'0'); ch=getchar();}
    return x*w;
}
const int N=3e5+10;
const int inf=0x3f3f3f3f;
int n, m;
struct node {int d, st, id;} a[N];
bool cmp(node a, node b) {return a.st<b.st;}
struct type {int p, t;} ;
vector<int> as[N];
struct trnode{
    int l, r, lc, rc, mn;
} tr[N<<2]; int trlen;
#define lc(x) tr[x].lc
#define rc(x) tr[x].rc
void pushup(int now) {
    tr[now].mn=min(tr[lc(now)].mn, tr[rc(now)].mn);
}
void build(int l, int r) {
    int now=++trlen;
    tr[now]={l, r, -1, -1, inf};
    if(l==r) {tr[now].mn=0; return ;}
    int mid=(l+r)>>1;
    tr[now].lc=trlen+1, build(l, mid);
    tr[now].rc=trlen+1, build(mid+1, r);
    pushup(now);
}
void update(int now, int l, int r, int c) {
    if(tr[now].l>=l&&tr[now].r<=r) {
        tr[now].mn=c; return ;
    }
    int mid=(tr[now].l+tr[now].r)>>1;
    if(l<=mid) update(lc(now), l, r, c);
    if(r>mid) update(rc(now), l, r, c);
    pushup(now);
}
type query(int now, int c) {
    if(tr[now].l==tr[now].r) return {tr[now].l, tr[now].mn};
    int L=(tr[lc(now)].mn>c)?(tr[lc(now)].mn-c):0;
    int R=(tr[rc(now)].mn>c)?(tr[rc(now)].mn-c):0;
    if(L<=R) return query(lc(now), c);
    else return query(rc(now), c);
}
signed main() {
    n=read(); m=read();
    for(int i=1;i<=n;i++) {
        a[i]={read(), read(), i};
    }
    sort(a+1, a+1+n, cmp);
    build(1, m);
    for(int i=1;i<=m;i++) update(1, i, i, 0);
    for(int i=1;i<=n;i++) {
        int now=a[i].st;
        type tp=query(1, now);
        as[tp.p].push_back(a[i].id);
        update(1, tp.p, tp.p, max(now, tp.t)+a[i].d); 
    }
    for(int i=1;i<=m;i++) {
        printf("%lld ", as[i].size());
        sort(as[i].begin(), as[i].end());
        for(int j:as[i]) printf("%lld ", j);
        puts("");
    }
    return 0;
}