暴力优化暴力

· · 休闲·娱乐

题目：P3380。

https://www.luogu.com.cn/discuss/1281459

测试数据范围更新

为卡掉 O(nm) 暴力，本题测试数据范围放大到 1\le n,m\le2\times10^5。若需参考在此日期之前编写的题解，请注意测试数据范围的变动。

原数据均已经放到不计分的 Subtask 中。

\textbf{Computers are fast nowadays, so we can solve this problem in O(nm)}. \textbf{It is important to make sure your program uses \red{SIMD} instructions.}

我们需要先通过 P2617，注意到暴力能过，说一下怎么写的，就是先离散化，使得每个值都不同，然后动态维护数组 pos 表示每个值的位置，查询时只要在值域上从左向右扫一遍，然后记录当前有多少个值在查询区间内，达到 k 时输出答案。然后你可能说这个东西不能 SIMD 啊，你不是要到达 k 后立即停止吗？没关系，SIMD 每次处理 8 个数，先将这 8 个数的贡献加上，然后判断是否达到 k，如果达到重新暴力扫一遍这 8 个数，只会扫一次，问题不大（此处 SIMD 记作优化 1）。

P3380 也是一样的可以做，再讲个优化：如果发现 k 大于当前查询区间长度的一半，可以改为倒着扫描值域，常数可以在极限 hack 数据上非常小，记为优化 2。

如果优化 1,2 都不写，甚至可以获得 98 分，任写一个即可通过。

我还没加快读，16.26s 已经比大多数的人的代码快了。