题解：P14268 [ROI 2015 Day2] 路灯

ycy1124 · 2025-12-18 16:49:28 · 题解

前置知识。

难度大部分在于代码。

思路

发现要求从开始到现在的答案，因此每次只需要考虑增加的答案即可。考虑设 f_i 表示以 i 为左端点最远能拓展到哪里，那么我们的答案就为 \sum_{i = 1}^nf_i - i + 1。初始的 f 数组预处理是简单的。

考虑修改。首先发现区间赋 0 不会影响答案，考虑区间赋 1。这时不难发现只会影响到与 l\sim r 联通的最长的连续 1 子段。这个最长子段可以用线段树求出来，这个具体做法放后面说。此时我们求出来了这个最长子段后，就只需要将这里面所有位置的 f_i 跟这个区间的右端点取 max 并统计贡献即可。这基本就是吉司机线段树的模板。

最后讲一下前面的子段怎么求，我们考虑直接将 1\sim l - 1 的所有在线段树上的节点先扣下来，然后从右至左遍历一下，如果当前区间全为 1 就继续找，否则我们就返回右端点开始的最长连续 1 的左端点。这个是很好在线段树上维护的。

代码

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 3e5 + 5;

struct Node {
    int l, r, mn, mn1, cnt, tagmn;
} tr[N << 2];

struct node {
    int l, r, lw, rw, tag;
} Tr[N << 2];

int n, m, ans, nxt[N];

string s;

#define mid (tr[p].l + tr[p].r >> 1)
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)
#define len(p) (Tr[p].r - Tr[p].l + 1)

__inline__ void Push_Up(int p) {
    tr[p].mn = min(tr[ls(p)].mn, tr[rs(p)].mn);
    tr[p].cnt = 0;

    if(tr[ls(p)].mn == tr[p].mn) {
        tr[p].cnt += tr[ls(p)].cnt;
    }
    else {
        tr[p].mn1 = min(tr[ls(p)].mn, tr[rs(p)].mn1);
    }

    if(tr[rs(p)].mn == tr[p].mn) {
        tr[p].cnt += tr[rs(p)].cnt;
    }
    else {
        tr[p].mn1 = min(tr[rs(p)].mn, tr[ls(p)].mn1);
    }

    if(tr[ls(p)].mn == tr[p].mn && tr[rs(p)].mn == tr[p].mn) {
        tr[p].mn1 = min(tr[ls(p)].mn1, tr[rs(p)].mn1);
    }
}

__inline__ void Build(int p, int l, int r) {
    tr[p].l = l, tr[p].r = r;

    if(tr[p].l == tr[p].r) {
        tr[p].mn = nxt[l];
        tr[p].mn1 = 1e9;
        tr[p].cnt = 1;
        return;
    }

    Build(ls(p), l, mid);
    Build(rs(p), mid + 1, r);
    Push_Up(p);
    return;
}

__inline__ void add(int p, int k) {
    if(k <= tr[p].mn) {
        return;
    }

    tr[p].mn = k;
    tr[p].tagmn = k;
}

__inline__ void Push_Down(int p) {
    if(!tr[p].tagmn) {
        return;
    }

    add(ls(p), tr[p].tagmn);
    add(rs(p), tr[p].tagmn);
    tr[p].tagmn = 0;
}

__inline__ void  Push_Date(int p, int l, int r, int k) {
    if(tr[p].mn >= k) {
        return;
    }

    if(tr[p].l >= l && tr[p].r <= r && tr[p].mn < k && tr[p].mn1 >= k) {
        ans += tr[p].cnt * (k - tr[p].mn);
        add(p, k);
        return;
    }

    Push_Down(p);

    if(l > mid) {
        Push_Date(rs(p), l, r, k);
    }
    else if(r <= mid) {
        Push_Date(ls(p), l, r, k);
    }
    else {
        Push_Date(ls(p), l, r, k);
        Push_Date(rs(p), l, r, k);
    }

    Push_Up(p);
}

#undef mid
#define mid (Tr[p].l + Tr[p].r >> 1)

__inline__ void push_up(int p) {

    if(Tr[ls(p)].lw == len(ls(p))) {
        Tr[p].lw = Tr[ls(p)].lw + Tr[rs(p)].lw;
    }
    else {
        Tr[p].lw = Tr[ls(p)].lw;
    }

    if(Tr[rs(p)].rw == len(rs(p))) {
        Tr[p].rw = Tr[ls(p)].rw + Tr[rs(p)].rw;
    }
    else {
        Tr[p].rw = Tr[rs(p)].rw;
    }
}

__inline__ void build(int p, int l, int r) {
    Tr[p].l = l, Tr[p].r = r, Tr[p].tag = - 1;

    if(l == r) {
        if(s[l] == '1') {
            Tr[p].lw = Tr[p].rw = 1;
        }

        return;
    }

    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    push_up(p);
}

__inline__ void push_down(int p) {
    if(Tr[p].tag == -1) {
        return;
    }

    if(Tr[p].tag == 1) {
        Tr[ls(p)].lw = Tr[ls(p)].rw = len(ls(p));
        Tr[ls(p)].tag = 1;
        Tr[rs(p)].lw = Tr[rs(p)].rw = len(rs(p));
        Tr[rs(p)].tag = 1;
    }
    else {
        Tr[ls(p)].lw = Tr[ls(p)].rw = 0;
        Tr[ls(p)].tag = 0;
        Tr[rs(p)].lw = Tr[rs(p)].rw = 0;
        Tr[rs(p)].tag = 0;
    }

    Tr[p].tag = -1;
}

__inline__ void push_date1(int p, int l, int r) {
    if(Tr[p].l >= l && Tr[p].r <= r) {
        Tr[p].lw = Tr[p].rw = len(p);
        Tr[p].tag = 1;
        return;
    }

    push_down(p);

    if(l > mid) {
        push_date1(rs(p), l, r);
    }
    else if(r <= mid) {
        push_date1(ls(p), l, r);
    }
    else {
        push_date1(ls(p), l, r);
        push_date1(rs(p), l, r);
    }

    push_up(p);
}

__inline__ void push_date0(int p, int l, int r) {
    if(Tr[p].l >= l && Tr[p].r <= r) {
        Tr[p].tag = 0;
        Tr[p].lw = Tr[p].rw = 0;
        return;
    }

    push_down(p);

    if(l > mid) {
        push_date0(rs(p), l, r);
    }
    else if(r <= mid) {
        push_date0(ls(p), l, r);
    }
    else {
        push_date0(ls(p), l, r);
        push_date0(rs(p), l, r);
    }

    push_up(p);
}

vector <int> id;

__inline__ void Get_id(int p, int l, int r) {
    if(Tr[p].l >= l && Tr[p].r <= r) {
        id.push_back(p);
        return;
    }

    push_down(p);

    if(l > mid) {
        Get_id(rs(p), l, r);
    }
    else if(r <= mid) {
        Get_id(ls(p), l, r);
    }
    else {
        Get_id(ls(p), l, r);
        Get_id(rs(p), l, r);
    }
}

__inline__ int findl(int x) {
    if(x < 1) {
        return 1;
    }

    id.clear();
    Get_id(1, 1, x);
    int w = x + 1;

    for(int i = id.size() - 1; i >= 0; i --) {
        if(Tr[id[i]].lw == len(id[i])) {
            w = Tr[id[i]].l;
        }
        else {
            return Tr[id[i]].r - Tr[id[i]].rw + 1;
        }
    }

    return w;
} 

__inline__ int findr(int x) {
    if(x > n) {
        return n;
    }

    id.clear();
    Get_id(1, x, n);
    int w = x - 1;

    for(auto it : id) {

        if(Tr[it].lw == len(it)) {
            w = Tr[it].r;
        }
        else {
            return Tr[it].l + Tr[it].lw - 1; 
        }
    }

    return w;
}

signed main() {
//  freopen("qwq.in", "r", stdin);
//  freopen("qwq.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    cin >> s;
    s = ' ' + s;

    bool vis = 0;
    int las = n;

    for(int i = n; i >= 1; i --) {
        if(s[i] == '0') {
            las = i - 1;
            nxt[i] = i - 1;
        } 
        else {
            nxt[i] = las;
        }
    }

    for(int i = 1; i <= n; i ++) {
        ans += nxt[i] - i + 1;
    }

    cout << ans << '\n';

    Build(1, 1, n);
    build(1, 1, n);

    for(int i = 1; i <= m; i ++) {
        int l, r, op;
        cin >> l >> r >> op;

        if(op == 1) {
            push_date1(1, l, r);
            int L = findl(l - 1), R = findr(r + 1);
            Push_Date(1, L, R, R);
        }
        else {
            push_date0(1, l, r);
        }

        cout << ans << '\n';
    }

    return 0;
}