I题 | 智乃挖坑

解题思路：

答案具有单调性，因此可以二分答案。已知挖的坑都是三角形，因此可以对差分数组求两次前缀和来构建这种三角形。每次操作复杂度都是 ，每次 的复杂度是 。

关于对差分数组求两次前缀和后的部分性质见下图（重点看 diff 和 pre2）：

示例代码：

int n, m, h;
pii op[N];
int pre[N], pre2[N];

bool check(int m) {
	vector<int> diff(n + 1);

	for (int i = 1; i <= m; ++i) {
		int p = op[i].x, f = op[i].y;

		if (p + 1 <= n) diff[p + 1] -= 2;
		if (p + 1 + f	<= n) ++diff[p + 1 + f];

		if (p + 1 - f > 0)++diff[p + 1 - f];
		else {
			diff[1] += 1 + f - p;
			if (n >= 2)diff[2] -= f - p;
		}
	}

	for (int i = 1; i <= n; ++i) {
		pre[i] = pre[i - 1] + diff[i];
		pre2[i] = pre2[i - 1] + pre[i];
		if (pre2[i] > h) return 0;
	}

	return 1;
}

// 二分模板
int search() {
	int l = 0, r = m + 1, mid;

	while (l + 1 != r) {
		mid = (l + r) / 2;
		if (check(mid))
			l = mid;
		else
			r = mid;
	}

	return r;
}

void solve() {
	cin >> n >> m >> h;
	for (int i = 1; i <= m; ++i) cin >> op[i].x >> op[i].y;
	int res = search();
	if (res > m)cout << "No";
	else cout << "Yes\n" << res;
}