自动搬运

查看原文

来自洛谷，原作者为

	BPG_ning And I dont wanna look back on life

搬运于2025-08-24 23:11:03，当前版本为作者最后更新于2025-03-14 20:11:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

豪牛鼻的题。

先考虑个做法，先默认所有操作都是区间加，然后将一个区间加变成补集加，等价于全局 $+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;
}