题解：CF1758F Decent Division

潘德理2010 · 2026-08-08 17:46:41 · 题解

因为需要每个区间内 1 和 0 的权值数量相等，所以考虑把 0 改为 -1，限制考虑区间内的和为 0。

考虑操作如何处理。先考虑 -1 变为 1。此时应该在当前区间的左右两边寻找 -1 并加入。如果找不到，说明左右两边都是一个区间，将这个区间并入当前区间后，继续在左右两边寻找 -1 并加入，直到总和为 0。

如果是 1 变为 -1，那么我们会得到一个总和为 -2 的区间，需要将两个 -1 从其中抽离。寻找第一个和为 -1 的前缀（可以使用线段树维护），这个前缀的最后一个数必定是 -1。将其抽离，此时区间的总和从 -2 变为 -1。再重复一遍操作，就可以从 -1 变为 0。

时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct sgt{
    #define mid ((le+ri)>>1)
    #define ls (u<<1)
    #define rs ((u<<1)|1)
    #define lp ls,le,mid
    #define rp rs,mid+1,ri
    int mn[N<<2];
    int t[N<<2];
    void push_up(int u){
        mn[u]=min(mn[ls],mn[rs]);
    }
    void ch(int u,int k){
        mn[u]+=k;
        t[u]+=k;
    }
    void push_down(int u){
        ch(ls,t[u]);
        ch(rs,t[u]);
        t[u]=0;
    }
    void init(int u,int le,int ri,int a[]){
        if(le==ri){
            mn[u]=a[le];
            return;
        }
        init(lp,a);
        init(rp,a);
        push_up(u);
    }
    void upd(int u,int le,int ri,int x,int y,int k){
        if(x<=le&&ri<=y){
            ch(u,k);
            return;
        }
        push_down(u);
        if(x<=mid) upd(lp,x,y,k);
        if(y>mid) upd(rp,x,y,k);
        push_up(u);
    }
    int que(int u,int le,int ri,int x,int y,int k){
        if(mn[u]>k) return -1;
        if(le==ri) return le;
        push_down(u);
        if(x<=mid){
            int w=que(lp,x,y,k);
            if(w!=-1) return w;
        }
        if(y>mid){
            int w=que(rp,x,y,k);
            if(w!=-1) return w;
        }
        return -1;
    }
    int get_pos(int u,int le,int ri,int x){
        if(le==ri){
            return mn[u];
        }
        push_down(u);
        if(x<=mid) return get_pos(lp,x);
        return get_pos(rp,x);
    }
}t;
int n=1e6,q,a[N],b[N];
set<pair<int,int>> s;
vector<pair<int,int>> del,ins;
pair<int,int> get_seg(int x){
    auto it=s.lower_bound({x,0});
    if(it!=s.end()&&it->first==x) return *it;
    if(it==s.begin()) return {-1,-1};
    --it;
    auto [l,r]=*it;
    if(l<=x&&x<=r) return {l,r};
    return {-1,-1};
}
void cal1(int l,int r,int cnt){
    if(!cnt){
        if(l<=r) ins.push_back({l,r});
        return;
    }
    int w=(l>1?t.get_pos(1,1,n,l-1):0); 
    int v=t.que(1,1,n,l,r,w-1);
    if(l<=v-1) ins.push_back({l,v-1});
    cal1(v+1,r,cnt-1);
}
void cal2(int l,int r,int cnt){
    if(!cnt){
        ins.push_back({l,r});
        return;
    }
    if(l!=1){
        auto [x,y]=get_seg(l-1);
        if(x==-1){
            cal2(l-1,r,cnt-1);
        }
        else{
            del.push_back({x,y});
            cal2(x,r,cnt);
        }
        return;
    }
    if(r!=n){
        auto [x,y]=get_seg(r+1);
        if(x==-1){
            cal2(l,r+1,cnt-1);
        }
        else{
            del.push_back({x,y});
            cal2(l,y,cnt);
        }
    }
    return;
} 
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>q;
    for(int i=1;i<=n;i++){
        a[i]=-1;
        b[i]=a[i]+b[i-1];
    }
    t.init(1,1,n,b);
    while(q--){
        int x;
        cin>>x;
        if(a[x]==1){// 1 to 0(-1)
            t.upd(1,1,n,x,n,-2);
            a[x]=-1;
            auto [l,r]=get_seg(x);
            del.push_back({l,r});
            cal1(l,r,2);
        }
        else{// 0(-1) to 1
            t.upd(1,1,n,x,n,2);
            a[x]=1;
            auto [l,r]=get_seg(x);
            if(l==-1) cal2(x,x,1);
            else{
                del.push_back({l,r});
                cal2(l,r,2);
            }
        }
        cout<<(int)del.size()<<"\n";
        for(auto [l,r]:del){
            cout<<l<<" "<<r<<"\n";
            s.erase({l,r});
        }
        cout<<(int)ins.size()<<"\n";
        for(auto [l,r]:ins){
            cout<<l<<" "<<r<<"\n";
            s.insert({l,r});
        }
        cout<<"\n";
        del=ins={};
    }
}