AT_dp_w Intervals 题解
chlchl
·
·
题解
看到题解里多多少少都有错误，我来补一篇，顺便纪念 700AC。
题意简述
给定 m 个形如 l_i,r_i,v_i 的命令，若一个长度为 n 的 01 串中，第 l_i\sim r_i 个位置至少有一个 1，则分数可以增加 v_i。问所有 01 串中的最大分数。
## 做法
对于这种区间的命令，一种常见的做法是化区间为点。具体来说，就是按照右端点排序，当访问到某个区间的右边界时才计算其贡献。
显然，分数的计算只跟 $1$ 的位置有关系，所以状态肯定是 $f_{i,j}$ 表示前 $i$ 个位置最后一个 $1$ 在 $j$ 位置的最大分数。
转移时，一开始我想着先枚举倒数第二个出现 $1$ 的位置 $k$，$f_{i,j}=f_{j-1,k}+\sum_{k<l_x\leq i,r_x=j}v_x$。但这样不仅正确性不保证，即使加上主席树优化，快速算出后面的 $\sum$，时间也去到 $O(n^3\log m)$，肯定过不了。
考虑换一种转移。刚刚枚举倒数第二个 $1$ 出现的位置是不必要的。因为我们的 $j\leq i$，所以前 $i-1$ 个位置的最后一个 $1$ 肯定也是 $j$（$j=i$ 时再另说）。
而 $f_{i,j}$ 比 $f_{i-1,j}$ 多的就是右端点在 $i$，左端点包含 $j$ 位置的所有命令的分数。
所以我们得到 $f_{i,j}=f_{i-1,j}+\sum_{l_k\leq j,r_k=i}v_k,j<i$。
当 $j=i$ 时，前 $i-1$ 个位置的最后一个 $1$ 可以是任意位置，所以在 $1\sim i-1$ 中取最大值，即 $f_{i,i}=\max_{j=1}^{i-1}f_{i-1,j}$。
当然，为了防止分数全负，我们还要对 $0$ 取个 $\max$。
时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$，肯定过不了。
空间优化比较爽，转移只与上一维有关，直接省去 $i$ 维即可。
时间就比较麻烦了。因为这个转移很难优化其中的 $\sum$ 部分。
所以换种角度思考。注意到方程中的 $l_k\leq j$，证明有很多 $f$ 值的更新都用到了同一个命令。我们能不能枚举结尾（即 $i$），对于每个命令，一次多个 $f$ 值来减少复杂度呢？
答案是肯定的。一个命令影响的的是一个连续的区间。我们把 $f$ 数组扔到线段树上，就可以通过命令的区间更新来快速处理了。
线段树的每个单点就表示 $f$ 数组的值，一段区间就表示 $f$ 数组一段区间的最大值。
对于符合 $r_j=i$ 的所有命令，每次将 $[l_j,r_j]$ 这个区间 $+v_j$，相当于将所有 $f_k(l_j\leq k)$ 全部加上当前命令的分数。
查询时直接输出 $1\sim n$ 的最大值即可。
注意，$f_{i,i}$ 的更新是在 $1\sim i-1$ 中取最大值，所以我们要额外做一次单点更新，每一次将 $i$ 这个位置加上 $\max_{j=1}^{i-1}\{f_j\}$。而因为 $i$ 后面的值还没更新，所以直接调用 $val_1$ 就是 $1\sim i-1$ 最大值。
总时间复杂度 $O(n\log n)$，空间复杂度 $O(4n)$，可以 AC。
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
int n, m;
struct order{
int l, r;
ll v;
bool operator < (const order &p) const {
return r < p.r;
}
} a[N];
ll val[N << 2], tag[N << 2];
#define ls(o) (o << 1)
#define rs(o) (o << 1 | 1)
void pushdown(int o){
val[ls(o)] += tag[o];
val[rs(o)] += tag[o];
tag[ls(o)] += tag[o];
tag[rs(o)] += tag[o];
tag[o] = 0;
}
void update(int o, int l, int r, int s, int t, ll x){
if(l >= s && r <= t){
val[o] += x;
tag[o] += x;
return ;
}
int mid = (l + r) >> 1;
pushdown(o);
if(s <= mid)
update(ls(o), l, mid, s, t, x);
if(t > mid)
update(rs(o), mid + 1, r, s, t, x);
val[o] = max(val[ls(o)], val[rs(o)]);
}//一课只有更新的线段树
int main(){
scanf("%d%d", &n, &m);
for(int i=1;i<=m;i++)
scanf("%d%d%lld", &a[i].l, &a[i].r, &a[i].v);
sort(a + 1, a + 1 + m);//排序，注意不是 n 条命令
for(int i=1,j=1;i<=n;i++){
update(1, 1, n, i, i, max(0ll, val[1]));//更新 i 位置
while(a[j].r == i && j <= m)
update(1, 1, n, a[j].l, a[j].r, a[j].v), j++;//更新线段
//运用双指针思想，均摊 O(1)
}
printf("%lld\n", max(0ll, val[1]));//与 0 取 max
return 0;
}
```