题目：智乃挖坑 ( 二次差分 + 二分 )

思路：题目要判断 m 次操作中，是否会出现某个位置的累计深度超过 h，并输出第一次越界的操作编号。

这是一个典型的 “最小可行解” 问题，具有单调性：

  • 如果前 x 次操作已经挖穿（深度 > h），那么任何 y > x 也一定会挖穿。

  • 如果前 x 次操作没有挖穿，那么任何 y < x 也不会挖穿。

因此可以对操作次数 mid 进行二分：

  • 检查前 mid 次操作是否越界。

  • 若越界，说明答案 ≤ mid，收缩右边界。

  • 若未越界，收缩左边界。

二分结束后，若找到的操作次数 ≤ m，输出 Yes 和该次数；否则输出 No。

这道题的核心巧妙之处在于用二阶差分将复杂的区间叠加操作转化为常数次单点修改，并结合二分答案将问题转化为判定性问题，从而把时间复杂度从不可行的暴力模拟优化到 O((n+m)log⁡m)

AC代码：时间复杂度O ( (n + m) long m )

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
using pii = pair<int, int>;
using pll = pair<ll, ll>;

bool can(ll m, vector<pll>& mv,ll n,ll h) {
    vector<ll> dd(n + 1);
    for (ll i = 1; i <= m; i++) {
        ll p = mv[i].first, f = mv[i].second;
        if (p - f + 1 < 1) {
            dd[1] += f - p + 1;
            dd[2] -= f - p;
        }
        else  dd[p - f + 1]++;
        if (p + 1 <= n) {
            dd[p + 1] -= 2;
        }
        if (p + f + 1 <= n) {
            dd[p + f + 1]++;
        }
    }
    ll f = 0, ff = 0;
    for (int i = 1; i <= n; i++) {
        ff += dd[i];
        f += ff;
        if (f > h) {
            return true;
        }
    }
    return false;
}


void solve() {
    ll n, m, h;
    cin >> n >> m >> h;
    vector<pair<ll, ll>> mv(m + 2);
    for (int i = 1; i <= m; i++ ) {
        ll p, f;
        cin >> p >> f;
        mv[i].first = p;
        mv[i].second = f;
    }
    ll l = 1, r = m + 1;
    while (l < r) {
        ll mid = (l + r) >> 1;
        if (can(mid, mv, n, h)) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    if (l <= m) {
        cout << "Yes" << endl;
        cout << l << endl;
    }
    else {
        cout << "No" << endl;
    }
}

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

总结：这道题把“区间加三角形”这一看似繁重的操作，通过两次差分神奇地转化为几个点的修改，淋漓尽致地体现了差分思想在压缩操作信息上的威力。再配上二分答案的框架，将动态判定变为静态检验，是处理大规模时序叠加问题的经典范本。

二阶差分的极致压缩：三次单点修改

对一阶差分再做一次差分（即二阶差分），这个三角形的“构造信息”会被压缩到至多三个点上：

  • 在 p - f + 1 处 +1 （斜率从 0 变成 +1）

  • 在 p + 1 处 -2 （斜率从 +1 变成 -1，变化量为 -2）

  • 在 p + f + 1 处 +1 （斜率从 -1 变回 0）

于是，每次操作只需在二阶差分数组的这 2~3 个位置进行 O(1)的加减。处理完所有操作后，通过两次前缀和（先恢复一阶差分，再恢复原数组）就能在 O(n)时间内得到任意次操作后的累计深度。这比用线段树、树状数组维护区间加等差数列更简洁且常数极小。