蝴蝶与花 题解

· · 题解

UPD on 2020.11.23

感谢神仙验题人 @QuantAsk 和 @beginend CCCCOrz。

这道题的 idea 最初来源于 P3514 [POI2011]LIZ-Lollipop，那道题利用其它性质可以 O(n) 预处理答案，O(1) 回答。并不支持修改操作。

然后有一天和 QuantAsk 讨论这题的时候想出了支持修改的 O(m\log n) 做法，然后就有了这道题 /fad。

看到有人说这道题卡常 /kk，将数据范围开这么大是因为 O(m\log^2 n) 做法常数实在是太小了，我尝试构造了很多数据都可以轻松跑过，所以最终只能在数据范围下手。

有神仙写线段树被卡常，但我和验题人的递归版线段树都是可以在不加 O2 下 2s 跑过的。至于有神仙写 Splay。。。那我真的感到抱歉了 /kel。

std 是树状数组，所以常数小一点，我尝试了很多次，在不加 O2 下都可以在 1s 内跑过。

题意简述

给出一个长度为 n 的 1,2 序列。要求支持单点修改，查询和为 k 且左端点尽量小的区间。

算法 1

枚举左端点，发现在左端点不断向右扫描的过程中，右端点的位置也一定单调不减。所以不用每次重新开始扫描右端点，在上一次扫描的基础上继续向右即可。

时间复杂度 O(nm)，期望得分 20pts。

算法 2

将原序列做前缀和，设做前缀和后的序列为 s，问题转化为求最小的两个位置 i,j 使得 s_j-s_i=k。

对于修改操作，相当于将序列 s 的一段后缀全部加上一个数；对于查询操作，可以枚举左端点，二分出右端点，如果这一段区间的和为 k 即为答案。

时间复杂度 O(nm\log n) 或 O(nm\log^2 n)，取决于是在数据结构内二分还是二分套数据结构。写的好看一些或许可以拿到 20pts。

甚至没有算法 1 优秀。

算法 3

在算法 2 中，容易发现我们二分出的每一段区间和要么是 k，要么是 k+1。因为如果和大于 k+1 的话，右端点向左移动一位和肯定不小于 k。

假设我们二分出的两个区间为 [l,r_1] 和 [l+1,r_2]，且这两个区间的和均为 k+1，那么：

最后一点换句话说，黄色部分的和一定等于蓝色部分的和，而蓝色部分的和为 2，那么只有当 r_2=r_1+1 且 a_{r_2}=2 时才满足条件。

那如果再加入一个区间 [l+2,r_3]，那么就有 a_{l+1}=a_{r2}=2,r_3=r_2+1。我们发现，只要接下来有一个位置不是 2 了，那么一定存在一个和为 k+1 的区间，也就是答案区间与连续的 2 的个数有关。

那么我们用数据结构维护前缀和，对于每一次询问，二分出从位置 1 开始和不小于 k 的区间 [1,p]。然后再用数据结构求出位置 1 和位置 p 后连续的 2 的个数，假设分别为 cnt1 个和 cnt2 个，

可以手写小数据来理解。

那么我们需要解决两个问题：

  1. 如何找到第一个前缀和不小于 k 的位置。

  2. 如何求出一个位置后面有多少个连续的 2。

对于问题 1，直接采用二分+数据结构即可。对于问题 2，依然可以二分长度，假设为 len，那么只需要判断区间 [p,p+len-1] 的和是否为 2\times len 即可。

采用树状数组或者线段树实现均可。

时间复杂度 O(m\log^2 n)，期望得分 50pts。

算法 4

可以在算法 3 的基础上，在数据结构内二分。可以省掉一个 \log。

树状数组二分或线段树二分均可，后者写法不优美可能会被卡。

时间复杂度 O(m\log n)，期望得分 100pts。