题解 | #小球投盒#

看到这个题第一眼没思路，第二眼直接上线段树区间修改，看了题解发现怪不得这题难度是简单最高赞题解妙啊

#include <bits/stdc++.h>

template<class T> struct Segt {
    struct node {
        int l, r;
        T w, rmq, lazy;
    };
    std::vector<T> w;
    std::vector<node> t;

    Segt() {}
    Segt(int n) { init(n); }
    Segt(std::vector<int> in) {
        int n = in.size() - 1;
        w.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            w[i] = in[i];
        }
        init(in.size() - 1);
    }

    #define GL (k << 1)
    #define GR (k << 1 | 1)

    void init(int n) {
        w.resize(n + 1);
        t.resize(n * 4 + 1);
        auto build = [&](auto self, int l, int r, int k = 1) {
            if (l == r) {
                t[k] = {l, r, 0, 0, -1};
                return;
            }
            t[k] = {l, r};
            int mid = (l + r) / 2;
            self(self, l, mid, GL);
            self(self, mid + 1, r, GR);
            pushup(k);
        };
        build(build, 1, n);
    }
    void pushdown(int k) {
        if (t[k].lazy == -1) return;
        pushdown(t[GL], t[k].lazy);
        pushdown(t[GR], t[k].lazy);
        t[k].lazy = -1;
    }
    void pushdown(node &p, T lazy) { 
        p.w = (p.r - p.l + 1) * lazy;
        p.lazy = lazy;
    }
    void pushup(int k) {
        auto pushup = [&](node &p, node &l, node &r) {
            p.w = l.w + r.w;
        };
        pushup(t[k], t[GL], t[GR]);
    }
    void modify(int l, int r, T val, int k = 1) {
        if (l <= t[k].l && t[k].r <= r) {
            t[k].w = val * (t[k].r - t[k].l + 1);
            t[k].lazy = val;
            return;
        }
        pushdown(k);
        int mid = (t[k].l + t[k].r) / 2;
        if (l <= mid) modify(l, r, val, GL);
        if (mid < r) modify(l, r, val, GR);
        pushup(k);
    }
    T ask(int l, int r, int k = 1) { // 区间询问
        if (l <= t[k].l && t[k].r <= r) {
            return t[k].w;
        }
        pushdown(k);
        int mid = (t[k].l + t[k].r) / 2;
        T ans = 0;
        if (l <= mid) ans += ask(l, r, GL);
        if (mid < r) ans += ask(l, r, GR);
        return ans;
    }
};

int main() {
    int n, m;
    std::cin >> n >> m;
    Segt<int> T(n + 1);
    int ans = -1;
    for (int i = 1; i <= m; i++) {
        int op, x;
        std::cin >> op >> x;
        if (op == 1) {
            T.modify(x, x, 1);
        } else {
            if (x > 1) T.modify(1, x - 1, 1);
            if (x < n) T.modify(x + 1, n, 1);
        }
        if (ans == -1) {
            if (T.ask(1, n) == n) {
                ans = i;
            }
        }
    }
    std::cout << ans << '\n';
}