NFLS0911T3

· · 个人记录

题意：给定一个长度为 n 的序列 a ， q 次询问，每次询问 l,r 之间满足 B-A<=C-B 的三元组 (A,B,C) 的权值最大值。权值的定义为 (A,B,C)=a_A+a_B+a_C
有限制的最大值不好求，甚至不可求。
这样一般需要一个关键观察。
上面那个限制条件其实就是 A 到 B 的距离不大于 B 到 C 的距离。那么假设三元组 (A,B,C) 是最优的三元组。
那么一定不存在 A<=x<=B 且 (a_x >a_A 或 a_x>a_B)
考虑反证法，如果存在，那么将小的那个替换为 x 答案一定增加且一定合法，因为 A,B 间的距离变小了，而 B,C 的距离不变或变大了。
这样的二元组 (A,B) 并不会很多，是 O(n) 级别，复杂度分析就是单调栈。
我们维护这样的二元组 (A,B)
考虑先将离线询问，挂到左端点然后扫描左端点。
维护 f_i 表示从对于当前 l ，取 i 作为 C 的最大权值。
我们考虑当 l \rightarrow l-1 时怎么样维护 f_i
首先 f_i 的 C 点已经确定，而且左端点只移动了一个位置，因此新增的贡献的 A 点也已经固定，就是 l-1 。这样已经固定了两个点， B 点只能取小于 mid=\frac{((l-1)+i)}{2}

我们把每个二元组 (A,B) 挂到 A 每次扩展将 l+1 扩展到 l ，枚举当前 A 到 l 的二元组，然后将 f_i 到 f_n i\ge 2\times B-A 更新一下，这个用线段维护一下就做完了。
每次查询最大值是 f_i+a_i
这个可以有初始权值的区间最大值线段树维护。