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

思路

比较简单的小签题。

让我们维护到时间 t_i 的等待时间最短编号最小的机器，于是用平衡树维护每个机器完成当前工作的时间，然后特殊的，每一个在 t_i 之前完成工作的机器都等待时间都相同而且至少有一个数，于是答案即平衡树上权值大于 t_i 与所有最小完成时间的最大值的编号最小值。

代码

#include<bits/stdc++.h>
#define int long long 
#define Maxn 1000005 
using namespace std;
int val[Maxn],sz[Maxn],id[Maxn],sgt[Maxn],minv[Maxn],lson[Maxn],rson[Maxn],prio[Maxn],rt,tot;
void pushup(int x) {
    minv[x] = val[x];
    if(lson[x])minv[x] = min(minv[x],minv[lson[x]]);
    if(rson[x])minv[x] = min(minv[x],minv[rson[x]]);
    sgt[x] = x;
    if(lson[x]&&id[sgt[lson[x]]] < id[sgt[x]])sgt[x] = sgt[lson[x]];
    if(rson[x]&&id[sgt[rson[x]]] < id[sgt[x]])sgt[x] = sgt[rson[x]];
    sz[x] = sz[lson[x]] + sz[rson[x]] + 1;
}
int NewNote(int k,int d) {
    id[++tot] = d;
    val[tot] = k;
    prio[tot] = rand();
    sz[tot] = 1;
    minv[tot] = val[tot];
    sgt[tot] = tot;
    return tot;
}
void split(int now,int bound,int Id,int &x,int &y) {
    if(!now)return x = y = 0,void();
    if(val[now] < bound||(val[now] == bound&&id[now] <= Id)) {
        x = now;
        split(rson[now],bound,Id,rson[now],y);
    } else {
        y = now;
        split(lson[now],bound,Id,x,lson[now]);
    } pushup(now);
}
int Merge(int x,int y) {
    if(!x || !y)return x + y;
    if(prio[x] <= prio[y]) {
        rson[x] = Merge(rson[x],y);
        pushup(x); return x;
    } else {
        lson[y] = Merge(x,lson[y]);
        pushup(y); return y;
    }
}
void Insert(int k,int d) {
    int x,y = NewNote(k,d),z;
    split(rt,k,d,x,z);
    rt = Merge(x,Merge(y,z));
}
vector<int> q[Maxn];
struct node {
    int s,t,id;
    bool operator<(const node&is)
    const{return t < is.t;}
} r[Maxn];
signed main()
{
//  freopen("print1.in","r",stdin);
//  freopen("print.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
//  cout<<n<<" "<<m<<"\n";
    for(int i=1;i<=m;i++)
        Insert(1,i);
    for(int i=1;i<=n;i++)
        cin>>r[i].s>>r[i].t,r[i].id = i;
    sort(r+1,r+1+n);
    for(int i=1;i<=n;i++) {
//      cout<<r[i].id<<" ";
        int s = r[i].s,t = r[i].t;
        int w = max(t,minv[rt]),x,y,z;
//      cout<<w<<" ";
        split(rt,w,m,x,y);
//      cout<<id[x]<<" "<<id[y]<<" ";
        // x 中含要找的 
        int p = sgt[x],w1 = val[p],I = id[p];
//      cout<<id[p]<<" "<<w1<<" "<<I<<"\n";
        q[I].push_back(r[i].id);
        rt = Merge(x,y);
        split(rt,w1,I-1,x,y);
        split(y,w1,I,y,z);
//      cout<<id[y]<<"\n";
        y = Merge(lson[y],rson[y]);
        rt = Merge(x,Merge(y,z));
        Insert(max(w1,t)+s,I);
    }
    for(int i=1;i<=m;i++) {
        cout<<q[i].size();
        if(q[i].size())cout<<" "; 
        sort(q[i].begin(),q[i].end());
//      for(int u:q[i])cout<<u<<" ";
        for(int j=0;j<(int)q[i].size();j++) {
            cout<<q[i][j];
            if(j != (int)q[i].size()-1)cout<<" ";
        }
        cout<<"\n";
    }
    return 0;
}