题解：P10711 [NOISG 2024 Prelim] Amusement Park

Cybrex · 2025-11-18 16:57:01 · 题解

两种团队的上车方式不同，所以分开处理。

又因为每个团队只会上车一次，所以我们可以暴力地修改每个团队的上车情况，并每次从当前编号最小的团队开始上车。

设置当前车剩下的名额为 b，对于下一个团队，如果能拆开，则直接让其上车，需要维护这类团队的编号的最小值，可以使用对顶堆维护。如果不能拆开，则要找到下一个能上车的团队，需要找到这类团队的下一个编号最小的价值小于等于 b 的位置，这个可以用线段树二分，或者平衡树维护。

复杂度 O(q \log q)

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+10;
const int INF=1e18;
struct node{
    int l,r,mn;
};
node tr[N*4];
#define ls u<<1
#define rs u<<1|1
inline void up(int u){
    tr[u].mn=min(tr[ls].mn,tr[rs].mn);
}
inline void build(int u,int l,int r){
    tr[u].l=l;tr[u].r=r;
    if(l==r){
        tr[u].mn=INF;
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    up(u);
}
inline void cg(int u,int x,int k){
    if(tr[u].l==x&&tr[u].r==x){
        tr[u].mn=k;
        return;
    }
    int mid=(tr[u].l+tr[u].r)>>1;
    if(x<=mid){
        cg(ls,x,k);
    }
    else{
        cg(rs,x,k);
    }
    up(u);
}
inline int find(int u,int x){
    if(tr[u].l==tr[u].r){
        return tr[u].mn<=x?tr[u].l:-1;
    }
    int ans=-1;
    if(tr[ls].mn<=x){
        ans=find(ls,x);
    }
    else if(tr[rs].mn<=x){
        ans=find(rs,x);
    }
    return ans;
}
struct Node{
    int id;
    bool operator<(const Node &x) const{
        return x.id<id;
    }
};
int ww[N];
priority_queue<Node> q,fq;
inline void qcl(){
    while(q.size()&&fq.size()&&q.top().id==fq.top().id){
        q.pop();fq.pop();
    }
}
int lx[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int qq;
    cin>>qq;
    int cnt=0;
    build(1,1,200000);
    for(int i=1;i<=qq;i++){
        int op;cin>>op;
        if(op==1){
            ++cnt;
            cin>>ww[cnt]>>lx[cnt];
            if(lx[cnt]==0){
                cg(1,cnt,ww[cnt]);
            }
            else{
                q.push({cnt});
            }
        }
        if(op==2){
            int x;cin>>x;
            if(lx[x]==0){
                cg(1,x,INF);
            }
            else{
                ww[x]=0;
                fq.push({x});
                qcl();
            }
        }
        if(op==3){
            int b;cin>>b;
            vector<int> ansid,ansvl;
            while(b){
                qcl();
                int fdw=find(1,b);
                if(!q.size()&&fdw==-1){
                    break;
                }
                else if(!q.size()&&fdw!=-1){
                    int id=fdw;
                    ansid.push_back(id);
                    ansvl.push_back(ww[id]);
                    cg(1,id,INF);b-=ww[id];
                }
                else if(q.size()&&fdw==-1){
                    int id=q.top().id;
                    if(ww[id]<=b){
                        ansid.push_back(id);
                        ansvl.push_back(ww[id]);
                        q.pop();b-=ww[id];
                    }
                    else{
                        ansid.push_back(id);
                        ansvl.push_back(b);
                        ww[id]-=b;b=0;
                    }
                }
                else{
                    if(q.top().id>fdw){
                        int id=fdw;
                        ansid.push_back(id);
                        ansvl.push_back(ww[id]);
                        cg(1,id,INF);b-=ww[id]; 
                    }
                    else{
                        int id=q.top().id;
                        if(ww[id]<=b){
                            ansid.push_back(id);
                            ansvl.push_back(ww[id]);
                            q.pop();b-=ww[id];
                        }
                        else{
                            ansid.push_back(id);
                            ansvl.push_back(b);
                            ww[id]-=b;b=0;
                        }
                    }
                }
            }
            cout<<ansid.size()<<endl;
            for(int j=0;j<ansid.size();j++){
                cout<<ansid[j]<<" "<<ansvl[j]<<endl;
            }
        }
    }

    return 0;
}