503

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<int> v(n + 2);
	for (int i = 1; i <= n; i++) cin >> v[i]; 
	for (int i = n; i >= 1; i--) v[i] -= v[i - 1];
 
	struct datas
	{
		int d, s, t;
	};
	vector<datas> k(m + 1);
	for (int i = 1; i <= m; i++) cin >> k[i].d >> k[i].s >> k[i].t;
 
	int l = 1, r = m, mid, ans;
	while (l <= r)
	{
		mid = l + (r - l) / 2;
		auto check = [&]() -> bool
		{
			auto b = v;
			for (int i = 1; i <= mid; i++)
			{
				b[v[i].s] -= v[i].d;
				b[v[i].t + 1] += v[i].d;
			}
			int ans = 0;
			for (int i = 1; i <= m; i++)
			{
				ans += b[i];
				if (b[i] < 0) return 1;
			}
			return 0;
		};
		if (check()) r = (ans = mid) - 1;
		else l = mid + 1; 
	}
	cout << ans;
}

Important

随着订单增加，每天可用教室的数量一定单调下降 我们可以二分求出第一天出现负值的订单编号 每个订单 我们会选择 $[L,R]$ 全部减去 $d$ 可以用差分来加速处理过程