P2801 tomato
简要题意
区间加,区间查询大于 \(k\) 的元素数量。
题解
发现 \(Polylog\) 无法胜任,考虑分块,块内维护有序序列即可。
record
LOJ6546 简单的数列题
简要题意
给定两个序列 \(\{a_n\},\{b_n\}\),要求支持
- 交换 \(b_x,b_y\)
- 对 \(\{a_n\}\) 区间加
- 求 \(\max_{i=l}^r\{a_i\cdot b_i\}\)
题解
先否决掉 \(Polylog\),考虑分块。
操作 1 仅会影响两个块,暴力修改即可。
接下来解决操作 23。由于使用分块,只需要考虑对整块的修改和查询。对于一个整块,问题相当于对于两个序列 \(\{a'_B\},\{b'_B\}\),我们需要支持让所有的 \(a'_i\) 加上一个数,求 \(\max\{a'_ib'_i\}\)。
记总的修改为 \(s\),即要求 \(\max\{(a'_i+s)b'_i\}\),在块内维护凸包,使用斜率优化即可。
注意到每次查询时使用的斜率单调递增,所以在凸包上查询是线性的;通过归并可以让建立凸包的复杂度也为线性,故精细维护下复杂度为 \(O(n\sqrt{n})\)
标签:题意,分块,max,查询,题解,序列 From: https://www.cnblogs.com/watware-cym/p/17560597.html