10.14 闲话：KTT
Part.1 基本算法
引入这样一个问题（其实这并不是板子，但是笔者认为这是此算法的另一种理解方式）：
luogu P5693 EI 的第六分块
区间加，区间最大子段和。
这东西有个十分重要的性质，所有加的数都是正数。
先考虑怎么单点修，这是山海经，只需维护 \(lmax, rmax, totmax, sum\)，竟然如此轻易。
那么现在扩展到区间修改：
首先肯定需要维护刚才提到的四个值，但是修改咋修改这些东西呢。
不难发现肯定就是形如区间加 \(len\times x\)，其中 \(len\) 表示这个值对应的区间长度。
那么转化一下就变为了每个节点维护 \(O(len)\) 个一次函数，每次横坐标加 \(x\)，询问最大值。
这的确是李超能做到的，但李超最难受的一点便是无法删除（只能撤销），那么如果只涉及这一个节点绝对是正确的，可是如果子节点被修改，那么 PushUp 就会修改区间内的线段，我们不得不暴力重构，这样就假了。
接下来接着挖掘性质，通过观察力可得：\(lmax, rmax, totmax\) 的区间长度单调不减，证明比较简单。
这启发了我们，也就是至多进行 \(O(n\log n)\) 次修改！
现在切入正题：
如果我们可以得知什么时候会发生上述区间长度的增长，那么复杂度就有了保证，可是如何维护这个问题呢，可以通过如下问题更直观的感受（这两个问题其实维护的信息基本一致，不过如下问题更为简洁）：
\(n\) 个 \(k_i x+b_i\) 的一次函数，每次区间给 \(x\) 加，区间询问最大值。
如图，不难发现，函数之间的大小关系是“单调”的，像这样的大小关系变换称为一次“击败”事件。
由此，可以维护出产生任意一次击败事件的最小的 \(\Delta x\) 当增加的 \(x\) 高过这个阈值就暴力重构。
惊奇的发现，这个击败事件其实就和上述的 \(lmax\) 等区间长度增长是很像的。
于是这样干复杂度大概就是 \(O(n\log^2 n)\) 的了，经过更严谨的势能分析可以发现是 \(O(n\log^3 n)\) 的，不过实际常数很小，可以近似看做 \(O(n\log^2 n)\)。
总复杂度：\(O((n+m)\log^3 n)\)
具体实现就是对于两个一次函数求交点，然后对这个交点的横坐标取个 \(min\) 就行。
回到原问题，既然已经知道了 \(lmax, rmax, totmax, sum\) 的更新方法，那么只需要对 \(lmax, rmax, totmax\) 三个转移的交点统统取 \(min\) 就好。
细节：
- \(\Delta x\) 要开浮点数。
- 可以封一个一次函数减小码量。
- 查询合并两个区间答案使用结构体更加便捷。
EI 的第六分块
#include <iostream>
#include <algorithm>using namespace std;const int N = 4e5 + 10;#define int long long
using ld = long double;
const ld double_inf = 1e100;class Poly
{public :int k, b;Poly operator + (Poly x){return {k + x.k, b + x.b};}Poly operator + (int x){return {k, b + k * x};}
};Poly max(Poly x, Poly y)
{if (x.b != y.b) return x.b < y.b ? y : x;return x.k < y.k ? y : x;
}ld calc(Poly x, Poly y)
{if (x.k == y.k) return double_inf;ld pos = (ld)(x.b - y.b) / (ld)(y.k - x.k);if (pos <= 0) return double_inf;return pos;
}struct Node
{int lmax, rmax, totmax, sum;friend Node operator + (Node x, Node y){Node tmp;tmp.sum = x.sum + y.sum;tmp.lmax = max(x.lmax, x.sum + y.lmax);tmp.rmax = max(y.rmax, y.sum + x.rmax);tmp.totmax = max({x.totmax, y.totmax, x.rmax + y.lmax});return tmp;}
};int a[N];class SemTree
{#define lid id << 1#define rid id << 1 | 1public :Poly lmax[N << 2], rmax[N << 2], totmax[N << 2], sum[N << 2];ld x[N << 2];int tag[N << 2], L[N << 2], R[N << 2];void PushUp(int id){sum[id] = sum[lid] + sum[rid];lmax[id] = max(lmax[lid], sum[lid] + lmax[rid]);rmax[id] = max(rmax[rid], sum[rid] + rmax[lid]);totmax[id] = max(max(totmax[lid], totmax[rid]), rmax[lid] + lmax[rid]);x[id] = min(x[lid], x[rid]);x[id] = min(x[id], calc(lmax[lid], sum[lid] + lmax[rid]));x[id] = min(x[id], calc(rmax[rid], sum[rid] + rmax[lid]));x[id] = min(x[id], min({calc(totmax[lid], totmax[rid]), calc(max(totmax[lid], totmax[rid]), rmax[lid] + lmax[rid])}));// x[id] = min(x[id], min({calc(totmax[lid], totmax[rid]), calc(totmax[lid], rmax[lid] + lmax[rid]), calc(totmax[rid], rmax[lid] + lmax[rid])}));}void Push(int id, int v){tag[id] += v;lmax[id] = lmax[id] + v;rmax[id] = rmax[id] + v;totmax[id] = totmax[id] + v;sum[id] = sum[id] + v;x[id] -= v;}void PushDown(int id){if (tag[id]){Push(lid, tag[id]), Push(rid, tag[id]);tag[id] = 0;}}void ReBuild(int id){if (x[id] <= 0){PushDown(id);x[id] = double_inf;ReBuild(lid), ReBuild(rid);PushUp(id);}}void Build(int id, int l, int r){x[id] = double_inf;L[id] = l;R[id] = r;if (l == r){Poly tmp = {1, a[l]};x[id] = double_inf, lmax[id] = rmax[id] = totmax[id] = sum[id] = tmp;return ;}int mid = (l + r) >> 1;Build(lid, l, mid), Build(rid, mid + 1, r);PushUp(id);}void Update(int id, int cl, int cr, int l, int r, int val){if (l <= cl && cr <= r) return Push(id, val);int mid = (cl + cr) >> 1;PushDown(id);ReBuild(id);if (l <= mid) Update(lid, cl, mid, l, r, val);if (r > mid) Update(rid, mid + 1, cr, l, r, val);PushUp(id);}Node Query(int id, int cl, int cr, int l, int r){if (l <= cl && cr <= r) return {lmax[id].b, rmax[id].b, totmax[id].b, sum[id].b};int mid = (cl + cr) >> 1;PushDown(id);ReBuild(id);if (r <= mid) return Query(lid, cl, mid, l, r);else if (l > mid) return Query(rid, mid + 1, cr, l, r);else return Query(lid, cl, mid, l, r) + Query(rid, mid + 1, cr, l, r);}
}T;signed main()
{// freopen("data.in", "r", stdin); freopen("data.out", "w", stdout);ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);int n, q; cin >> n >> q;for (int i = 1; i <= n; i++) cin >> a[i];T.Build(1, 1, n);for (int i = 1; i <= q; i++){int op, l, r; cin >> op >> l >> r;if (op == 1){int x; cin >> x;T.Update(1, 1, n, l, r, x);}else{cout << max(0ll, T.Query(1, 1, n, l, r).totmax) << '\n';}}return 0;
}
Part.2 例题
这东西出现概率还是蛮低的。
一道比较好的题：CF 1830F