题解：P11880 [RMI 2024] 选区间 / Choose Interval

· · 题解

豪牛鼻的题。

先考虑个做法，先默认所有操作都是区间加，然后将一个区间加变成补集加，等价于全局 +1，区间 -2。

枚举至多做了 k 次补集加，那么问题被转化为：给定序列，你能选出 k 个区间 -2，最后答案 +k。这个问题可以二分答案，对序列扫描线，优先队列维护区间最远的右端点，每次贪心取出最远的右端点进行区间 -2，可以做到 O(n^2\log^2n)。

令序列最大值为 m，先二分答案 mid，考虑有结论：k\in[m-mid,m-mid+1]。

证明：

先证明下界，因为做一次操作最大值至多 -2，全局 +1，所以一次操作后最大值至多 -1，那么希望最大值 \leq mid 就至少要做 m-mid 次操作。

证明上界。

另 k=m-mid。

定义 x 合法指存在方案选择 x 个区间进行区间 -2 使得全局 \leq mid-x。

考虑证明若 k+d+2 合法，则 k+d 合法（d \geq 0）。

若这 k+d+2 个区间里存在两个区间不交，那么把这两个区间操作删去，得到 k+d 个区间，其全局最大值至多 +2，所以 k+d 合法。

若这 k+d+2 个区间两两有交，设交集内最大值为 x。若 x> mid-(k+d)-4，意味着区间减之前 x'=x+2(k+d+2)>mid+k+d=m+d\geq m，矛盾。所以 x\leq mid-(k+d)-4，此时选出两个区间使得这两区间的交为所有区间的交（这两个区间显然一定存在），将这两个区间删去，使得 k+d 合法。

若 k,k+1 不合法，那么就不存在 k+d+1 合法，所以我们只需要在二分时 check k,k+1 的合法性。

于是我们 O(n\log^2n) 地做完了！

代码：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define fir first
#define sec second
#define mp make_pair
void chkmin(int &x,int y){x=min(x,y);}
void chkmax(int &x,int y){x=max(x,y);}
const int N=4e5+10,inf=1e9+10;
int n,q,a[N],f[N],t[N],pid[N];
vector<int> H[N];
struct node{int l,r;} Q[N];
void read(){
    cin>>q;
    n=q*2+1;
    for(int i=1;i<=q;i++){
        cin>>Q[i].l>>Q[i].r;
        H[Q[i].l].push_back(i);
        a[Q[i].l]++,a[Q[i].r+1]--;
    }
    for(int i=1;i<=n;i++) a[i]+=a[i-1];
}
int chk(int m,int V){
    V-=m;
    for(int i=0;i<=n;i++) t[i]=0;
    for(int i=1;i<=q;i++) pid[i]=1;
    priority_queue<pii,vector<pii>,less<pii> >q;
    while(!q.empty()) q.pop();
    int cnt=0,d=0;
    for(int i=1;i<=n;i++){
        d+=t[i];
        for(int p:H[i]){
            q.push(mp(Q[p].r,p));
        }
        while(d+a[i]>V){
            if(q.empty() || q.top().fir<i) return 0;
            pii p=q.top();
            q.pop();
            pid[p.sec]=0;
            t[p.fir+1]+=2;
            d-=2;
            cnt++;
            if(cnt>m) return 0;
        }
    }
    return 1;
}
void work(){
    int Max=0;
    for(int i=1;i<=n;i++) chkmax(Max,a[i]);
    int L=0,R=q;
    while(L<R){
        int mid=(L+R)>>1;
        if(chk(Max-mid,mid) || chk(Max-mid+1,mid)) R=mid;
        else L=mid+1;
    }
    cout<<L<<'\n';
    if(chk(Max-L,L)){
        for(int i=1;i<=q;i++) cout<<pid[i];
        cout<<'\n';
    }else{
        chk(Max-L+1,L);
        for(int i=1;i<=q;i++) cout<<pid[i];
        cout<<'\n';
    }
}
int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    read();
    work();
    cerr<<1.0*clock()/CLOCKS_PER_SEC<<'\n';
    return 0;
}