AT_dp_w Intervals 题解
题目链接: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;
}
参考文献: