KTT

写课件写着写着开始学 KTT 了是怎么回事。

KTT 解决的基本问题形如，给定 \(n\) 个一次函数 \(k_ix_i+b_i\)，区间对 \(x_i\) 加正数，查询区间一次函数的值的最大值。

考虑尝试维护每个位置的最大线段交换的阈值 \(t\)，即这个位置的儿子两个线段 \(l_1,l_2\)，目前是 \(l_1\) 为 \(\max\)，对 \(x_i\) 再加超过 \(t\) 就变成 \(l_2\) 为 \(\max\) 了。这个显然在 pushup 的时候要取 \(\min\)。

然后区间加 \(x\) 的时候就直接递归到 \(t\geq x\) 的节点打上标记就行了，记得把阈值减去 \(x\)。

可以证明时间复杂度是 \(O((n+q)\log^3 n)\) 的，但是因为目前 OI 界还不会卡，所以复杂度可以理解为常数略大一点的 2log。

P5693 EI 的第六分块

给定一个整数序列 \(a\)，支持两种操作：

• 1 l r x 表示给区间 \([l,r]\) 中每个数加上 \(x\)
• 2 l r 表示查询区间 \([l,r]\) 的最大子段和（可以为空）

\(1\le n,q \le 4\times 10^5\)，\(|a_i| \le 10^9\)，\(1 \le x \le 10^6\)。

如果把区间加变成单点加，我们就可以用正常的线段树来维护最大子段和，我们此时需要维护 \((lmx,rmx,ans,sum)\)。

把这四个信息看成一次函数放到 KTT 上，阈值变成 使得任意函数的取值来源变化的最小的 \(x\)。合并之类的都是一样正常合并就行了，只需要注意修改的时候递归到合适的位置即可。

合并的时候，加法就是单纯的把真实值和斜率加起来，所以我们不显式维护 \(x_i\) 的值，而是只维护斜率和真实值。下放标记的时候，不难发现贡献可以直接放到真实值上，因为这里的斜率就是这个信息所对应的区间的长度。

EI 证明了这样做的时间复杂度是 3log 的。

事实上，因为 OI 界目前不会卡这个东西，涉及到 KTT 并且只加正数或者只加负数的标记大概都可以看做是正确的复杂度。

P6792 [SNOI2020] 区间和

有一个长度为 \(n\) 的整数数列 \(a_1,a_2,\cdots,a_n\)（可能含有负数）。现在对其进行 \(q\) 次操作，每次操作是以下二者之一：

• 0 l r x 表示对于 \([l,r]\)，将 \(a_i\) 赋值为 \(\max(a_i,x)\)；
• 1 l r 求区间 \([l,r]\) 的最大子段和。即：\(\max(0, \max_{l\le u\le v\le r} (\sum_{i=u}^v a_i))\)。

\(1\le n\le10^5, 1\le q\le 2\times 10^5, |a_i|, |x|\le 10^9\)。

加强的疑似有点多了。

首先取 \(\max\) 部分用 segbeats 做，问题变成区间的所有 \(\min\) 加上某个正数。

首先显然这两部分是完全独立的计算复杂度的。

注意到如果直接按上面做，这个操作是不能直接贡献到 \(x_i\) 的。所以我们把斜率维护成 \(\min\) 值个数，这样就能直接贡献了。虽然没人证，但是普遍认为这样复杂度还是 3log 的。

说实话我是真的不想写这个题代码，太史了，写错一个地方调半年啊。

AT 的某个题

会在课件亮相。是一个 KTT 优化 DP 题，伊娜做过。