题解| #小球投盒#

我看题解都是用map或者set然后分类讨论，那我发一个使用二分加前缀和的思路。我们可以离线把操作记录下来然后二分最少需要几次可以全部覆盖。每次二分我们可以把前mid次操作通过差分和前缀和完成。具体可以看代码

#include<bits/stdc++.h>

using i64 = long long;

void DAOQI() {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> p(n + 2);

    std::vector<std::pair<int, int>> Q(m + 1);
    for (int i = 1; i <= m; i++) std::cin >> Q[i].first >> Q[i].second;

    auto check = [&](int mid) {
        std::fill(p.begin(), p.end(), 0);
        for (int i = 1; i <= mid; i++) {
            auto [op, x] = Q[i];
            if (op == 1) {
                p[x]++, p[x + 1]--;
            } else {
                if (x > 1) p[1]++, p[x]--;
                if (x < n) p[x + 1]++;
            }
        }
        for (int i = 1; i <= n; i++) {
            p[i] += p[i - 1];
            if (p[i] == 0) return false;
        }
        return true;
    };
    int l = 1, r = m, ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T = 1;
    //std::cin >> T;
    while (T--) DAOQI();
    return 0;
}