KTT

· · 算法·理论

KTT

例题：EI的第六分块

题意：区间加正数，区间最大子段和

做法：首先我们考虑如果不带区间加法如何做，显然我们可以维护ls,rs,sum,ans,这样时间复杂度是O(n\log n)

那么我们考虑带上区间加法后会有什么影响：我们考虑将一个区间视为一个一次函数y=kx+b，表示这个区间的和为b,给这个区间加上1，区间和的大小会加上k（即区间的大小）

我们再考虑一次修改对答案可能的影响，假设原本的线段为k_1x+b_1,新的线段是k_2x+b_2，那么如果k_1<k_2\and b_1>b_2，就有可能在修改时导致答案变化。

所以我们对于线段树上每一个区间记录一个x，表示当增量达到x时线段会被取代。

那我们考虑如何修改线段，一种非常朴素的想法是暴力重构整棵子树，看起来时间复杂度是O(n^2\log n)的，但实际上好像是O((n+q)\log^3 n)的

证明(还在理解，先D下来）:

首先我们考虑只维护ls,rs的复杂度，因为k只会变大，所以每个一次函数只会在他的每个祖先被更新一次，所以复杂度O(n\log n)

然后考虑维护ans的复杂度，考虑一次从左右侧ans到suf+pre的情况

在只被全局加的情况下，一个点从原来取两侧 ans 变成取 suf + pre 会发生 O(n log n) 次（即在两侧孩子 suf 和 pre 改变的情况下），而它的变化又可能导致 log n 个祖先的变化，每一次变化都需要一个线段树操作来更新，因此这里的时间复杂度为 O(n log^3^ n)。

区间加就相当于修改了 O(log n) 个节点的 suf 和 pre，它们可能在 k 不变大的情况下再进行一次 ans取 suf + pre，因此这里的时间复杂度为 O(m log^3^ n)。

调了两天两个发现最大子段和w.ans=max(max(u.ans,v.ans),u.rs+v.ls);打成w.ans=max(max(w.ls,w.rs),u.rs+v.ls);