[数据结构与算法]差分+贪心模拟

Division
题意：
给定一个正整数序列 $a$ 以及 $k$，每次操作可以选择一个区间 $[l,r](r?l+1>=k)$，然后把区间内的每个数除以 $2$ 向下取整。问是否能通过一些操作使得所有数变为 $1$，如果可以，请输入操作次数最少的具体操作方案，如果有多种输出任意一种。
思路：
对于给定的每个数预处理一下可以操作的次数
然后问题就变成了，每次可以选择一个合法的区间，对区间内所有数减 $1$，是否存在操作使得最后的数全部为 $0$
先对数列进行差分，最后目标是用最少的操作次数使得差分数组 $[1,n+1]$ 全为 $0$
注意我们差分时只能使区间减 $1$，也就是

a[l]--, a[r+1]++;

模拟思路就出来了，每次拿出左边一个 $>0$ 的和右边一个 $<0$ 的匹配
然后贪心地尽量把数组全变成 $0$ 就好了
这个用一个栈维护左端点用于匹配，用队列也一样，每次都是两个点进行匹配消除就好了
code：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define eps 1e-6
using namespace std;
const int maxn = 2e6 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
int a[maxn], cnt;
struct node{
	int l, r;
}ans[maxn];
void init(){
	for(int i = 1; i <= n + 1; ++i) a[i] = 0;
	cnt = 0;
}
void work()
{
	cin >> n >> m;
	init();
	for(int i = 1; i <= n; ++i){
		ll x;cin >> x;
		while(x > 1) ++a[i], x >>= 1;
	}
	for(int i = n + 1; i >= 1; --i) a[i] -= a[i-1];
	stack <int> s;
	for(int i = 1; i <= n + 1; ++i){
		if(i - m >= 1){
			while(a[i-m] > 0) s.push(i-m), a[i-m]--;
		}
		else {
			if(a[i] < 0){
				cout << -1 << endl;return;
			}
		}
		while(a[i] < 0)
		{
			if(s.empty()) {
				cout << -1 << endl;return;
			}
			ans[++cnt] = {s.top(), i - 1};
			s.pop();
			++a[i];
		}
	}
	if(!s.empty()){// 必须恰好匹配完
		cout << -1 << endl;return;
	}
	cout << cnt << endl;
	for(int i = 1; i <= cnt; ++i) cout << ans[i].l << " " << ans[i].r << endl;
}

int main()
{
	ios::sync_with_stdio(0);
	int TT;cin>>TT;while(TT--)
	work();
	return 0;
}