NFLSPC #2 LinQin 题解

2019-11-29 16:36:45 By wzy

$type=0$ 是给莫队的,$m \le 10^5$ 是给按序列分块的(不过好像没卡掉)

做法 1

把区间排序,最后的答案必然在相邻两项中产生。不妨考虑值域分块,即按照值所在的范围把原序列划分为若干个子序列。

不妨令块大小为 $B$,经过这样的划分之后,一次询问必然能分成 $\frac{n}{B}$ 个区间,每个区间在对应的值域块内。

对于每个值域块,用区间 dp 预处理出答案,复杂度 $O(nB)$;对于跨块的情况,不难发现只需要计算某个区间最大值和最小值,st 表即可。

因此总复杂度 $O(nB+\frac{nm}{B})$,$B=\sqrt {nm}$ 最优,复杂度 $O(n\sqrt m)$。

做法 2

考虑从前向后扫统计以当前位置结尾,每个位置作为开头的答案。不妨假设大的元素必然是靠后的那个,考虑找到当前前缀中最大的、且比当前位置小的数字,它能够产生一个前缀的贡献;再找到最大数字到当前数字这个区间中最大的、且小于当前的数字……一个一个更新计算贡献即可,贡献大概是个区间 set,可以用线段树维护。

这样的做法会被卡到 $O(n^2logn)$,因此可以思考一下性质。假设当前元素为 $x$,找到的最大值为 $a$,$a$ 右边找到的最大值为 $b(b < a < x)$。如果 $b$ 和 $x$ 计算了贡献,那么 $b$ 必须满足 $a \ge \frac{x+b}{2}$ 才能进行更新,否则 $a,b$ 会产生更优的贡献。

因此总共只需要更新 $O(\log 10^9)$ 个元素,强制在线可以用主席树维护区间 set,总复杂度 $O(n\log n\log 10^9)$。

评论

avatar
MagicSpark
这题莫队怎么做啊 n sqrt(n) log n过不了 莫队有没有n sqrt(n)的做法

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。