有人帮我看一下牛客周赛116E题吗？用的线段树维护，但是只过了一部分

提交链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=80185176

E

这道题我们可以先求出构造出个区间，这个区间是满足题目要求的最少区间数，如果，那么显然我们无法完成构造，否则可以通过拆分这个区间来达到个区间。

先看无解情况：或者。

预处理：用用来存的所有下标；我们构造一棵线段树，可以满足区间修改以及区间查询最小值；用来记录要加入的区间。

令表示已经对区间操作过次，现在来解决还需要对这个区间操作的次数，很显然次数等于，那么我们把区间加入个到中，然后进行区间修改，这时候区间原来为mn的位置肯定把这个大区间划分为多个小区间，假设原来区间中值为的下标为，那么我们继续处理子区间。

而值为的下标可以通过数组找到，就记录了的所有值为的下标，我们二分选出内的就好。

已经过了，加了一个线段树上二分找第一个最小位置，不用，哦耶终于过了。 AC代码：

#include <bits/stdc++.h>
using namespace std;
#define inf 1e18
#define endl '\n'
//#define int long long
#define lc u<<1
#define rc u<<1|1
typedef  long long ll;
typedef pair<int, int> pii;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 2e5 + 9, M = 2e5 + 9, mod = 1e9 + 7;
int a[N];
int n, m;
struct node {
	int l, r, mn;
	int lz;
} tr[N * 4];
void pushup(int u) {
	tr[u].mn = min(tr[lc].mn, tr[rc].mn);
}
void pushdown(int u) {
	if (tr[u].lz) {
		tr[lc].mn = tr[lc].mn - tr[u].lz;
		tr[rc].mn = tr[rc].mn - tr[u].lz;
		tr[lc].lz += tr[u].lz;
		tr[rc].lz += tr[u].lz;
		tr[u].lz = 0;
	}
}
void build(int u, int l, int r) {
	tr[u] = {l, r, a[l], 0};
	if (l == r) return;
	int mid = (l + r) / 2;
	build(lc, l, mid);
	build(rc, mid + 1, r);
	pushup(u);
}
void update(int u, int l, int r, int k) {
	if (tr[u].l >= l && tr[u].r <= r) {
		tr[u].mn -= k;
		tr[u].lz += k;
		return;
	}
	pushdown(u);
	int mid = (tr[u].l + tr[u].r) / 2;
	if (l <= mid) update(lc, l, r, k);
	if (r > mid) update(rc, l, r, k);
	pushup(u);
}
int query(int u, int l, int r) {
	if (tr[u].l >= l && tr[u].r <= r) return tr[u].mn;
	pushdown(u);
	int mid = (tr[u].l + tr[u].r) / 2;
	int res = inf;
	if (l <= mid) res = min(res, query(lc, l, r));
	if (r > mid) res = min(res, query(rc, l, r));
	return res;
}
//获取区间[l,r]最小的元素的下标
int get_first_mn(int u, int l, int r, int mn) {
	if (tr[u].l > r || tr[u].r < l) return -1;
	if (tr[u].l == tr[u].r) {
		if (tr[u].mn == mn) return tr[u].l;
		else return -1;
	}
	pushdown(u);
	//先看u的左边
	int res = -1;
	if (tr[lc].mn <= mn) {
		res = get_first_mn(lc, l, r, mn);
	}
	if (res != -1) return res;

	return get_first_mn(rc, l, r, mn);
}
bool ok = false;
vector<pii> seg;
int mx = 0, sum = 0;
//f(l,r)表示对区间[l,r]进行减区间mn，将这些区间加入seg中，之后根据最小元素进行分段
void f(int l, int r) {
	if (l > r || l < 1 || r > n || ok) return;
	int mn = query(1, l, r);
	for (int i = 1; i <= mn; i++) {
		seg.push_back({l, r});
	}
	update(1, l, r, mn);
	if (seg.size() > m) {
		ok = true;
		return;
	}
	int pos = get_first_mn(1, l, r, 0);
	if (pos == -1) return;
	f(l, pos - 1);
	f(pos + 1, r);
}
void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		mx = max(mx, a[i]);
		sum += a[i];
	}
	if (m < mx || m > sum) {
		cout << -1 << endl;
		return;
	}
	build(1, 1, n);
	f(1, n);
	int cnt = seg.size();
	if (m < cnt || ok) {
		cout << -1 << endl;
		return;
	}
	sort(seg.begin(), seg.end(), [&](pii x, pii y) {
		return x.second - x.first > y.second - y.first;
	});
	vector<pii> ans;
	int i = 0; //表示在第几个区间拆分后刚好加上[i+1,]刚好m个
	for (; i < seg.size(); i++) {
		cnt--;
		auto[l, r] = seg[i];
		if (r - l + 1 + cnt <= m) {
			for (int j = l; j <= r; j++) {
				ans.push_back({j, j});
			}
			cnt += r - l + 1;
		} else {
			int x = m - cnt + l - 2;
			for (int j = l; j <= x; j++) {
				ans.push_back({j, j});
			}
			ans.push_back({x + 1, r});
			cnt = m;
		}
		if (cnt == m) break;
	}
	for (i = i + 1; i < seg.size(); i++) {
		ans.push_back(seg[i]);
	}
	for (auto[l, r] : ans) {
		cout << l << " " << r << endl;
	}

}
/*

*/
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}