思路
看到时限这么大，考虑暴力做法。
我们将原序列分为 \(\text{B}\) 个块，每个块类似线段树三一样的维护 \(add,maxadd\)，表示这一块需要加的值，加的值的历史最大值。
同时对于每个数可以维护一个真实值与一个历史最值。
那么下传标记可以写成这样。
inline void push(int p)
{
fro(i, L[p], R[p])
sum[i] = max(sum[i], a[i] + madd[p]),
a[i] = a[i] + add[p];
add[p] = madd[p] = 0;
}
考虑所有数 \(\le x\) 的限制。
有一个很暴力的想法是，对于散块我们我们直接遍历，整块时二分解决问题。
那么对于每个块我们可以在开始构建与重构时进行排序维护。
inline void make(int p)
{
iota(s + L[p], s + R[p] + 1, L[p]);
sort(s + L[p], s + R[p] + 1, [&](int x, int y){
return a[x] < a[y];
});
num[L[p]] = sum[s[L[p]]];
fro(i, L[p] + 1, R[p]) num[i] = max(num[i - 1], sum[s[i]]);
fro(i, L[p], R[p]) b[i] = a[s[i]];
}
其中，\(num\) 是前缀历史最大值的最值。
同样，在修改时，我们整块可以只维护标记，而散块需要下传重构。
inline void upd(int l, int r, int x)
{
push(pos[l]);
fro(i, l, r) a[i] = a[i] + x, sum[i] = max(sum[i], a[i]);
make(pos[l]);
}
inline void change(int l, int r, int x)
{
if(pos[l] == pos[r])
return upd(l, r, x);
upd(l, R[pos[l]], x);
upd(L[pos[r]], r, x);
fro(i, pos[l] + 1, pos[r] - 1)
add[i] = add[i] + x,
madd[i] = max(madd[i], add[i]);
}
这样，就在 \(O(n\sqrt{n}\log n)\) 的时间复杂度解决了这个题，\(40s\) 的时限下还是绰绰有余。
可能可以通过分散层叠做到严格根号，但是不需要了。
Code
AC记录。