AT_dp_w Intervals 题解

题意：

给定 $m$ 条规则形如 $(l_i,r_i,a_i)$，对于一个 01 串，其分数的定义是：

对于第 $i$ 条规则，若该串在 $[l_i,r_i]$ 中至少有一个 $1$，则该串的分数增加 $a_i$。

你需要求出长度为 $n$ 的 01 串中的最大分数。

输入格式：

第一行 $n,m$ ，接下来 $m$ 行 $l_i,r_i,a_i$ 。

输出格式：

输出字符串的最大得分。

数据范围：

$1 \le n,m \le 2\times 10^5$ 且 $1\le l_i \le r_i\le n,~|a_i|\le 10^9$

这道题和 P9871 [NOIP2023] 天天爱打卡思路挺像的。

设 $f(i,j)$ 为前 $i$ 个位置中，上一个 $1$ 放在 $j$ 的最优方案，则

$f(i,0) = 0,\ f(i,i) = \max_{0 \le j < i} f(i-1,j) \\[6pt] f(i,j) = f(i - 1, j) + \sum_{l_k \le j \le r_k \le i} a_k \quad (j < i)$

后面这个东西可以把线段（即规则）按右端点排序，这样每次枚举 $r_k=i$ 的线段即可。

注意到对于线段 $(l_k,r_k)$ ，任何 $j \in [l_k, r_k]$ 的 $f(i-1,j)$ 都可以吃到 $a_k$ ，这就是一个区间修改

考虑用线段树维护每一轮的 $f(i,j)$ ，而不是用传统的滚动数组维护。

这样我们枚举 $i$ 的时候，就可以一轮区间加了，注意 $f(i,i)$ 要单独修改。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)

struct line { int l, r, v; } a[N];
struct node { int mx, tag; } tr[N * 4];
int n, m;
void push_up(int at) { up(tr[at].mx = tr[ls(at)].mx, tr[rs(at)].mx); }
void proc(int at, int v) { tr[at].mx += v; tr[at].tag += v; }
void push_down(int at)
{ 
    proc(ls(at), tr[at].tag);
    proc(rs(at), tr[at].tag); tr[at].tag = 0;
}
void build(int at, int l, int r)
{
    if(l == r) return ;
    push_down(at); int mid = (l + r) >> 1;
    build(ls(at), l, mid); build(rs(at), mid + 1, r); push_up(at);
}
void Modify(int x, int v, int at = 1, int l = 1, int r = n)
{
    if(l == r) return tr[at].mx += v, void(0);
    push_down(at); int mid = (l + r) >> 1;
    if(x <= mid) Modify(x, v, ls(at), l, mid);
    else Modify(x, v, rs(at), mid + 1, r);
    push_up(at);
}
void update(int nl, int nr, int v, int at = 1, int l = 1, int r = n)
{
    if(nl <= l && r <= nr) return proc(at, v);
    push_down(at); int mid = (l + r) >> 1;
    if(nl <= mid) update(nl, nr, v, ls(at), l, mid);
    if(nr > mid) update(nl, nr, v, rs(at), mid + 1, r);
    push_up(at);
}
int query(int nl, int nr, int at = 1, int l = 1, int r = n)
{
    if(nl <= l && r <= nr) return tr[at].mx;
    push_down(at); int mid = (l + r) >> 1, mx = -INF;
    if(nl <= mid) up(mx, query(nl, nr, ls(at), l, mid));
    if(nr > mid) up(mx, query(nl, nr, rs(at), mid + 1, r));
    return mx;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> a[i].l >> a[i].r >> a[i].v;
    sort(a + 1, a + 1 + m, [](line a, line b) { return a.r < b.r; });
    build(1, 1, n);
    for(int i = 1, p = 1; i <= n; i++)
    {
        Modify(i, max(0ll, tr[1].mx));
        while(p <= m && a[p].r == i) { update(a[p].l, i, a[p].v), ++p; }
    }
    cout << max(tr[1].mx, 0ll) << '\n';
    return 0;
}