E 小红的区间构造

线段树+二分+模拟

题意需要我们去求出是否存在恰好m个区间在的范围中，对第个位置的覆盖次数恰好是
考虑的上界因为区间最短可以恰好只包含一个点，那么对于最多的区间个数就是

再考虑最少的区间个数就多少，那么贪心一下，我们需要每次覆盖尽可能的长的区间长度，那么就可以简单的模拟一下，这个过程，枚举一下从~，以为左端点操作尽可能长的区间，我写的时候是把每一个都变成需要怎样操作区间，那么就是找到以为左端点某一个点为右端点的最长区间，并且

这样就可以用线段树维护一下区间最小值，然后每次二分右端点，找到最远满足条件的位置，然后这整个区间减去这个区间的最小值，反复上述操作直到，之后将区间用vector<pair<int,int>>存一下，还有对应的次数，因为一个区间只能覆盖一次，我们每次减去这整个区间的最小值，相当于用这同一个区间覆盖了很多次
现在我们就求出了最少区间的方案情况，之后就是给区间排一下序让最长的排后面，从最少的区间数不断划分增加，模拟一下每次给当前区间不断划分就行了

具体可以看代码(我写的还是很臃肿的)，思路大概就是这样，可以自己写一下

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ld = long double;
using PII=pair<ll,ll>;
using PIII=pair<int,pair<int,int>>;
const ld ESP = 1e-10;
const ld PI = acosl(-1);
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dis(1, 100);
const int N=1e6+10;
const int M=2e5+10;
// const int mod = 1000000007;
const int mod = 998244353;
ll a[M];
struct Tr{
    int lz;
    int Mi;
    int l,r;
}tr[M<<2];
void pushup(int p){
    tr[p].Mi=min(tr[p<<1].Mi,tr[p<<1|1].Mi);
}
void pushdown(int p){
    if(tr[p].lz){
        int v=tr[p].lz;
        tr[p<<1].Mi-=v;
        tr[p<<1|1].Mi-=v;
        tr[p<<1].lz+=v;
        tr[p<<1|1].lz+=v;
        tr[p].lz=0;
    }
}
void build(int p,int l,int r){
    tr[p].l=l;
    tr[p].r=r;
    tr[p].lz=0;
    if(l==r){
        tr[p].Mi=a[l];
        return ;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(p);
}
void add(int p,int L,int R,int k){
    if(tr[p].r<L||tr[p].l>R)return ;
    if(tr[p].l>=L&&tr[p].r<=R){
        tr[p].Mi-=k;
        tr[p].lz+=k;
        return ;
    }
    pushdown(p);
    if(L<=tr[p<<1].r){
        add(p<<1,L,R,k);
    }
    if(R>=tr[p<<1|1].l){
        add(p<<1|1,L,R,k);
    }
    pushup(p);
}
int query(int p,int L,int R){
    if(tr[p].r<L||tr[p].l>R)return 1e9;
    if(tr[p].l>=L&&tr[p].r<=R){
        return tr[p].Mi;
    }
    pushdown(p);
    return min(query(p<<1,L,R),query(p<<1|1,L,R));
}
void solve(){
    int n,m;
    cin>>n>>m;
    ll sum=0,res=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    build(1,1,n);
    vector<pair<int,int>> ans,ry;
    map<pair<int,int>,int> cnt;
    for(int i=1;i<=n;i++){
        while(query(1,i,i)){
            int l=i,r=n;
            int lx=i,rx=i;
            while(l<=r){
                int mid=l+r>>1;
                if(query(1,i,mid)!=0){
                    rx=mid;
                    l=mid+1;
                }
                else{
                    r=mid-1;
                }
            }
            int k=query(1,lx,rx);
            add(1,lx,rx,k);
            ans.push_back({lx,rx});
            cnt[{lx,rx}]+=k;
            res+=k;
        }
    }
    sort(ans.begin(),ans.end(),[&](pair<int,int> a,pair<int,int> b){
        return a.second-a.first+1<b.second-b.first+1;
    });
    if(m<=sum&&m>=res){
        ll now=res;
        while(now<m){
            pair<int,int> p=ans.back();
            cnt[p]--;
            if(!cnt[p]){
                ans.pop_back();
            }
            int L=p.second-p.first+1;
            if(now-1+L<=m){
                for(int i=p.first;i<=p.second;i++){
                    ry.push_back({i,i});
                    cnt[{i,i}]++;
                }
                now+=L-1;
            }
            else{
                int cz=m-now;
                for(int i=p.first;i<=p.first+cz-1;i++){
                    ry.push_back({i,i});
                    cnt[{i,i}]++;
                }
                ry.push_back({p.first+cz,p.second});
                cnt[{p.first+cz,p.second}]++;
                now+=cz;
            }
        }
        set<pair<int,int>> s;
        for(int i=0;i<ans.size();i++){
            s.insert(ans[i]);
        }
        for(int i=0;i<ry.size();i++){
            s.insert(ry[i]);
        }
        for(auto [x,y]:s){
            for(int i=1;i<=cnt[{x,y}];i++){
                cout<<x<<" "<<y<<'\n';
            }
        }
    }
    else{
        cout<<-1<<'\n';
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _=1;
    // cin>>_;
    while(_--){
        solve();
    }
    return 0;
}