题解 P6528 【「Wdoi-1」完美冻结】

· · 题解

按照题意模拟，构建出数表。查询时暴力枚举。
复杂度 \mathcal{O}(n^3+qn^2) ，期望得分 10 分。

记 (i,j) 位置处的数字为 f_{ij}

则

f_{ij}=\lfloor \frac{\sum_{x=min(i,j)}^{max(i,j)}a_x}{k} \rfloor

所以 \mathcal{O}(n^2) 构造数表，查询时利用二维前缀和即可。

时间复杂度为 \mathcal{O}(n^2+q)，期望得分 20 分。

过渡：

对于之后的子任务，n 非常大，所以我们很难还原出整个数表。

为了方便起见我们不妨将问题转化到数列上：

记 a_i 前缀和为 s_i，对于询问 l_1,r_1,l_2,r_2，答案为

\sum_{l_1\le i \le r_1}\sum_{l_2 \le j \le r_2}\lfloor \frac{s_j-s_{i-1}}{k} \rfloor

根据 [l_1,r_1]，[l_2,r_2] 两个区间的位置关系(相离，相交，包含)，我们有不同的容斥策略将所求化为若干个 \sum_{l\le i \le r}\sum_{l \le j \le r}\lfloor \frac{s_j-s_{i-1}}{k} \rfloor 的形式，此处留给读者自行思考。

所以经过一番转化，我们的问题转化成了如下形式，即求解

\sum_{l\le i \le r}\sum_{l \le j \le r}\lfloor \frac{s_j-s_{i-1}}{k} \rfloor $$\sum_{l\le i \le r}\sum_{l \le j \le r}( s_j-s_{i-1} )$$ 简单算一下每个 $s$ 的出现次数即可。 复杂度 $O(q)$ ，期望得分 $35$分。 - 子任务 $6 考虑另 $c_i= \lfloor \frac{s_i}{2} \rfloor,d_i=s_i\bmod 2$，则 $s_i=2c_i+d_i$，此时 $\lfloor \frac{s_j-s_{i}}{2} \rfloor=(c_j-c_i)-[d_j<d_i]

发现作差的两个 s 是错位的，所以我们进行简单地容斥：

\sum_{i=l}^{r}\sum_{j=i}^{r}\lfloor \frac{s_j-s_{i-1}}{2} \rfloor=\sum_{i=l}^{r-1}\sum_{j=i+1}^{r-1}\lfloor \frac{s_j-s_i}{2} \rfloor+\sum_{j=l}^{r}\lfloor \frac{s_j-s_{l-1}}{2}\rfloor+\sum_{i=l}^{r}\lfloor \frac{s_r-s_{i-1}}{2}\rfloor-\lfloor \frac{s_r-s_{l-1}}{2}\rfloor

记 p_i=\sum_{j=1}^{i}c_j，P_i=\sum_{j=1}^{i}p_j，C_i=\sum_{j=1}^{i}j*c_j

\sum_{j=l}^{r}\lfloor \frac{s_j-s_{l-1}}{2}\rfloor=\sum_{j=l}^{r}((c_j-c_{l-2})-[d_j<d_{l-1}])=p_r-p_{l-1}-(r-l+1)c_{l-1}-\sum_{j=l}^{r}[d_j<d_{l-1}]

由于 d_i 只有 01 两种取值，因此开一个记录 1 位置的树状数组通过差分即可求出\sum_{j=l}^{r}[d_j<d_{l-1}]

$$\sum_{i=l}^{r}\sum_{j=i+1}^{r}\lfloor \frac{s_j-s_i}{2} \rfloor=\sum_{i=l}^{r}\sum_{j=i+1}^{r}((c_j-c_i)-[d_j<d_i])=\sum_{i=l}^{r}\sum_{j=i+1}^{r}(c_j-c_i)-\sum_{i=l}^{r}\sum_{j=i+1}^{r}[d_j<d_i]$$ 左式 $=\sum_{i=l}^{r}(\sum_{j=i+1}^{r}c_j-(r-i)c_i)=\sum_{i=l}^{r}(p_r-p_i-r*c_i+i*c_i)=(r-l+1)p_r-(P_r-P_{l-1})-r(p_r-p_{l-1})+C_r-C_{l-1}

由于 d_i 只有 01 两种取值，因此使用线段树维护区间 0,1 的个数和逆序对个数即可求出右式

复杂度 \mathcal{O}(n\log n)，期望得分 50 分

q=1$ 且询问区间为 $[1,n]

仿照子任务6，求出 c_i= \lfloor \frac{s_i}{k} \rfloor,d_i=s_i\bmod k，化简步骤相同

与子任务 $4$ 算法结合，期望得分 $70$ 分 - 子任务 $5

在 6,4 的基础上，算法的瓶颈是需要求出 \sum_{i=l}^{r}\sum_{j=i+1}^{r}[d_j<d_i]，即区间逆序对个数

由于询问不强制在线，可以使用二次离线莫队 \mathcal{O}(n\sqrt{n}) 求解

其次就是 \sum_{j=l}^{r}[d_j<d_{l-1}] 的求解，这个可以将 d_i 和询问排序后用双指针+树状数组的方法 \mathcal{O}(n\log n) 求解

时间复杂度 \mathcal{O}(n\sqrt{n}+n\log n)，空间复杂度 \mathcal{O}(n)，可以通过此题