P14268 [ROI 2015 Day2] 路灯 题解

namespace lowspeed_song {

inline void init() {
}

int a[N];
char s[N];

struct Node {
    int l, r, sum, mx, tag;
    inline void init(int p) { l = r = p, mx = sum = a[p], tag = -1; }
    inline void push(int v) { sum = (r - l + 1) * v, mx = tag = v; }
} tree[N << 2];

inline Node operator+(const Node &l, const Node &r) {
    return {l.l, r.r, l.sum + r.sum, max(l.mx, r.mx), -1};
}

inline void build(int l, int r, int rt) {
    if (l == r) return tree[rt].init(l);
    int mid = l + r >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

inline void pushdown(int rt) {
    if (~tree[rt].tag) {
        tree[rt << 1].push(tree[rt].tag);
        tree[rt << 1 | 1].push(tree[rt].tag);
        tree[rt].tag = -1;
    }
}

inline void mdf(int rt, int ll, int rr, int v) {
    int &l = tree[rt].l, &r = tree[rt].r;
    if (ll <= l && r <= rr) return tree[rt].push(v);
    int mid = l + r >> 1; pushdown(rt);
    if (ll <= mid) mdf(rt << 1, ll, rr, v);
    if (mid < rr) mdf(rt << 1 | 1, ll, rr, v);
    tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

inline int find(int rt, int ll, int rr, int v) {
    int &l = tree[rt].l, &r = tree[rt].r;
    if (r < ll || rr < l) return -1;
    if (tree[rt].mx < v) return -1;
    if (l == r) return l;
    int mid = l + r >> 1; pushdown(rt);
    int res = find(rt << 1, ll, rr, v);
    if (~res) return res;
    return find(rt << 1 | 1, ll, rr, v);
}



inline void sol() {
    int n, q; cin >> n >> q;
    scanf("%s", s + 1);
    set<pair<int, int>> seg;
    for (int i = 1; i <= n; ++i) {
        if (s[i] == '0') a[i] = i - 1;
        else {
            int j = i;
            while (j < n && s[j + 1] == '1') ++j;
            seg.emplace(i, j);
            for (int k = i; k <= j; ++k) a[k] = j;
            i = j;
        }
    } build(1, n, 1);
    cout << tree[1].sum - n * (n - 1) / 2 << '\n';
    function<void(int, int)> turn_off = [&](int l, int r) {
        auto it = seg.lower_bound({l, -1});
        if (it != seg.begin() && prev(it)->second >= l) it = prev(it);
        vector<pair<int, int>> add;
        while (it != seg.end() && it->first <= r) {
            int L = it->first, R = it->second;
            it = seg.erase(it);
            if (L < l) add.emplace_back(L, l - 1);
            if (r < R) add.emplace_back(r + 1, R);
        } for (auto &[l, r] : add) seg.emplace(l, r);
    };
    function<pair<int, int>(int, int)> turn_on = [&](int l, int r) {
        auto it = seg.lower_bound({l, -1});
        int L = l, R = r;
        if (it != seg.begin() && prev(it)->second + 1 >= l) it = prev(it);
        while (it != seg.end() && it->first <= R + 1)
            L = min(L, it->first), R = max(R, it->second), it = seg.erase(it);
        seg.emplace(L, R);
        return pair<int, int>{L, R};
    };
    while (q--) {
        int l, r, c; cin >> l >> r >> c;
        if (!c) turn_off(l, r);
        else {
            auto [L, R] = turn_on(l, r);
            int p = find(1, L, R, R);
            if (p == -1) p = R + 1;
            if (p > L) mdf(1, L, p - 1, R);
       } cout << tree[1].sum - n * (n - 1) / 2 << '\n';
    }
}

} // namespace lowspeed_song