题解：P16725 [GKS 2019 #A] Contention

lailai0916 · 2026-08-31 09:05:02 · 题解

题意简述

有 n 个连续座位和 m 个区间订单。按某种顺序处理订单时，一个订单得到其区间内所有尚未分配的座位。

求一种处理顺序，使所有订单所得座位数的最小值尽可能大，输出这个最大值。

解题思路

从最后处理的订单开始考虑。在当前剩余订单中，记 g_i 为只被订单 i 覆盖的座位数。

若将 i 放在最后，则它恰好得到这 g_i 个座位：其他座位都至少属于一个更早处理的订单，已经被占用。因此可以选择 g_i 最大的订单作为最后一个，将它删除，再继续确定倒数第二个。

下面证明这个贪心。固定目标下界 k，假设当前订单存在一个满足要求的顺序。这个顺序的最后一个订单一定有至少 k 个独占座位，所以最大的 g_i 也至少为 k。

把我们选择的订单 i 从该顺序中移到最后，其后的其他订单少了一个竞争者，获得的座位数不会减少；原本在 i 前面的订单不受影响。订单 i 最后获得 g_i\ge k 个座位，因此调整后的顺序仍然合法。删除 i 后可以重复这个论证。

于是，只要存在最小分配数至少为 k 的顺序，贪心全过程就不会选出独占数小于 k 的订单。反过来，将贪心删除顺序反转，就是一个实际处理顺序，每个订单得到的座位数恰为它被删除时的独占数。因此，删除过程中所有选中 g_i 的最小值就是答案。

删除订单后，其他订单的独占座位数只增不减。一个座位对剩余订单产生新的贡献，仅发生在它的覆盖次数从 2 降为 1 时；初始覆盖次数为 1 的座位也要计入。

覆盖次数只会下降，每个座位至多被这样处理一次。我们不必在每次删除后重新统计所有订单。

先将所有 L_i,R_i+1 离散化为 a_1<a_2<\dots<a_s。相邻端点间的整数座位具有完全相同的覆盖订单集合，可以整体处理。第 j 段是 [a_j,a_{j+1})，长度为 a_{j+1}-a_j。

每段维护两个量：覆盖次数，以及所有覆盖订单编号的异或和。删除订单 i 时，在它覆盖的所有段上将次数减 1，异或和再异或 i。当覆盖次数等于 1 时，异或和就是唯一剩余订单的编号，将这一整段的长度加入该订单的 g_i。

线段树维护尚未计入贡献的段的最小覆盖次数，并支持区间减一和区间异或。若某个节点的最小值为 1，向下寻找对应叶子，取得唯一订单编号并更新贡献。

已经处理过的叶子将最小值改为足够大的哨兵值，今后不再报告；初始没有被任何订单覆盖的叶子也直接屏蔽。后续至多执行 m 次减一，哨兵值仍然远大于 1，不会被误认为新独占段。区间异或标记只用于把覆盖订单集合的变化传到叶子，不需要维护整段订单编号的聚合值。

用最大堆保存订单的当前独占数。独占数增加时插入一个新条目，不必删除旧条目；取堆顶时，丢弃已删除订单的条目，以及数值不等于当前 g_i 的过期条目。每个订单初始还要放入一个数值为 0 的条目，保证没有独占座位时仍能正确选择订单，最终答案也会变为 0。

一次删除后的收集过程中，所有未屏蔽段的覆盖次数仍至少为 1：次数为 1 的段此前已经被屏蔽，所以不会有未屏蔽段直接降到 0。这保证了节点最小值不为 1 时可以安全跳过，而不会漏掉其内部的新独占段。

每个离散段最多收集一次，总共只有 O(m) 次贡献增加与堆插入。删除订单的区间更新、收集叶子和堆操作各花费 O(\log m)，总时间复杂度为 O(m\log m)，空间复杂度为 O(m)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using pii=pair<int,int>;
const int N=60005;
const int inf=0x3f3f3f3f;
int a[N],L[N],R[N],s[N],b[N],cnt[N];
bool vis[N];
priority_queue<pii> q;
struct SEG
{
    int val[N<<2],sum[N<<2],tag[N<<2],xr[N<<2];
    void push_up(int u)
    {
        val[u]=min(val[u<<1],val[u<<1|1]);
    }
    void gx(int u,int x,int y)
    {
        val[u]+=x;
        tag[u]+=x;
        sum[u]^=y;
        xr[u]^=y;
    }
    void push_down(int u)
    {
        gx(u<<1,tag[u],xr[u]);
        gx(u<<1|1,tag[u],xr[u]);
        tag[u]=xr[u]=0;
    }
    void build(int u,int l,int r)
    {
        tag[u]=xr[u]=sum[u]=0;
        if(l==r)
        {
            val[u]=s[l]?s[l]:inf;
            sum[u]=b[l];
            return;
        }
        int mid=(l+r)>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        push_up(u);
    }
    void update(int u,int l,int r,int x,int y,int k)
    {
        if(x<=l&&r<=y){gx(u,-1,k);return;}
        push_down(u);
        int mid=(l+r)>>1;
        if(x<=mid)update(u<<1,l,mid,x,y,k);
        if(y>mid)update(u<<1|1,mid+1,r,x,y,k);
        push_up(u);
    }
    void query(int u,int l,int r)
    {
        if(val[u]!=1)return;
        if(l==r)
        {
            int id=sum[u];
            cnt[id]+=a[l+1]-a[l];
            q.push({cnt[id],id});
            val[u]=inf;
            return;
        }
        push_down(u);
        int mid=(l+r)>>1;
        query(u<<1,l,mid);
        query(u<<1|1,mid+1,r);
        push_up(u);
    }
}seg;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    int _=0;
    while(T--)
    {
        _++;
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=m;i++)
        {
            cin>>L[i]>>R[i];
            R[i]++;
            a[i*2-1]=L[i];
            a[i*2]=R[i];
            cnt[i]=vis[i]=0;
        }
        sort(a+1,a+m*2+1);
        int len=unique(a+1,a+m*2+1)-a-1;
        fill(s,s+len+1,0);
        fill(b,b+len+1,0);
        q=priority_queue<pii>();
        for(int i=1;i<=m;i++)
        {
            L[i]=lower_bound(a+1,a+len+1,L[i])-a;
            R[i]=lower_bound(a+1,a+len+1,R[i])-a;
            s[L[i]]++;
            s[R[i]]--;
            b[L[i]]^=i;
            b[R[i]]^=i;
            q.push({0,i});
        }
        for(int i=1;i<len;i++)s[i]+=s[i-1],b[i]^=b[i-1];
        seg.build(1,1,len-1);
        seg.query(1,1,len-1);
        int ans=n;
        for(int i=1;i<=m;i++)
        {
            while(vis[q.top().second]||q.top().first!=cnt[q.top().second])q.pop();
            int u=q.top().second;
            q.pop();
            ans=min(ans,cnt[u]);
            vis[u]=1;
            seg.update(1,1,len-1,L[u],R[u]-1,u);
            seg.query(1,1,len-1);
        }
        cout<<"Case #"<<_<<": "<<ans<<'\n';
    }
    return 0;
}