题解 P2464【[SDOI2008]郁闷的小J】
UperFicial
·
·
题解
二分+分块
前言
注意，这份题解适于大部分学分块的初学者，对于算法可能讲得很细，但分块的前置简单芝士不会提及。
逗比题，我也挺逗比连分块都能写锅掉
讲个不一样的做法，看到楼下都用的平衡树或是 map，这里给个二分+分块的 \texttt{naive} 做法。
题目连接：\text{Link}
题意简述
给定长度为 n 的序列 a，支持两种操作：
-
将 a_k 更改为 x。
-
询问区间 [l,r] 有多少个数等于 x。
### 题目分析
这道题教练放在平衡树作业里，但菜鸡我怎么看都不像是平衡树
发现 $1\le n,m\le 10^5$，而且要求区间统计个数，于是可以考虑 $O(n\sqrt n)$ 的分块。
对于 `C` 操作，显然直接更改 $a_k$ 即可。
而对于 `Q` 操作，如果 $x,y$ 在同一块里，暴力统计即可，复杂度 $O(\sqrt n)$，否则我们可以先暴力统计边角的两块，复杂度仍然为 $O(\sqrt n)$，但对于中间的块还暴力统计的话 $O(n\sqrt n)$ 直接上天。
于是就可以用分块中一个比较套路的做法，我们额外再设一个数组 $val$，对于一个下标范围为 $[l,r]$ 的块，$val_l$ 至 $val_r$ 对应 $a$ 数组在 $[l,r]$ 从小到大排序过后的值。
所以说当我们做更改操作即 `C` 操作时，我们先要更改 $a$，而且那一个块中的 $val$ 的值也要**重新赋值**后排序。
对于查询操作，暴力统计的时候一定要统计 $a$ 的值，因为 $val$ 中存的排过序的值，查询的那个边角的区间中的 $val$ 的值不一定对应它真实的值。
但对于中间的那些块，就能直接查 $val$ 了，因为这是后中间的那一坨跟顺序已经没关系了。
那对于中间的某个块 $i$，怎么快速查此块内等于 $k$ 的元素个数呢？
**二分**。因为我们的 $val$ 在排好序后就满足单调性了。
然后发现 `lower_bound` 能求 $\ge k$ 的最小的位置，而 `upper_bound` 能求 $>k$ 的最小位置，两者分别求一下位置得到 $p_1,p_2$，等于 $k$ 的元素一定就在 $[p_1,p_2-1]$ 这个区间。
只不过还要特判一下：
- 没有合法的 $p_1$，说明此块没有与 $k$ 相等的元素，直接 `continue` 掉。
- 有合法的 $p_1$ 却没有合法的 $p_2$，说明 $[p_1,r_i]$ 这个区间都为 $k$ 了。
然后就是算区间长度就没了。
时间复杂度：$O(n\sqrt n\log\sqrt n)$，带个 $\log$ 是因为既要排序还要二分，在 $n,m\le 10^5$ 之下很轻松。
空间复杂度：$O(n)$。
[$AC$ 链接](https://www.luogu.com.cn/record/51444126)
[$code$](https://paste.ubuntu.com/p/nvtGnSB5mK/)
求赞
$$\texttt{The End.by UF}$$