title: ' 学习笔记2022-12-31 '
date: 2022-12-31 14:00:03
tags:
- '离散化'
- 分块
- 数论分块
- 操作分块
- 根号分治
categories:
- 笔记
- 学习笔记
2022-12-31
离散化
把值域很大的一组数映射到值域较小的一组数，相对关系不变
P3740 [HAOI2014]贴海报：记录线段的关键点（如左端点右端点中点）进行离散化，因为 \(M\) 很小，暴力 for 即可。
扫描线
扫描线引入：
P1496 火烧赤壁：（矩形面积并一维版本）记录左右端点，排序，把每个区间变成两个关键的事件。
P5490 【模板】扫描线：求矩形面积并。把一个矩形拆成在第 \(y_1\) 列开始产生 \((x_1,x_2)\) 贡献，第 \(y_2\) 列结束 \((x_1,x_2)\) 贡献，线段树维护当前的列上有哪些地方有贡献。
对于矩形面积并的应用：
UVA1608不无聊的序列 Non-boring sequences：对于每一个位置 \(i\)，记录这个位置的数上一次和下一次出现的位置 \(pre\) 和 \(nxt\)，则这个区间有唯一元素当且仅当左端点在 \((pre,i]\) 内，右端点在 \([i,nxt)\)。于是可以将其对应二维平面一个矩形。后做矩形面积并，判断是否整个平面被覆盖即可。
数论分块
简单来说，\(\lfloor\dfrac{n}{i}\rfloor\) 只有 \(O(\sqrt{n})\) 种取值。
P1403 [AHOI2005]约数研究（加强版UVA11526）：考虑转换计数对象，考虑每个 \(i\) 是多少个数的因数，即问题转化为对 \(\lfloor\dfrac{n}{i}\rfloor\) 求和。
int f(int n) {
int ans = 0;
for(int i=1,j; i<=n; i=j+1)
j = n / (n/i), ans += (n/i) * (j-i+1);
return ans;
}
P2424 约数和：即 \(\sum_{i=1}^{n}{i\times\lfloor\dfrac{n}{i}\rfloor}\)，对于多出来的 \(\times i\) 计算每一项时做等差数列求和即可。
\[\begin{aligned} \sum_{i=1}^{n}{k\bmod i} &= \sum_{i=1}^{n}{k-i\times\lfloor\dfrac{k}{i}\rfloor}\\ &= n\times k - \sum_{i=1}^{n}{i\times\lfloor\dfrac{k}{i}\rfloor} \end{aligned} \]操作分块
类似于回滚莫队 （我不会
P6578 [Ynoi2019] 魔法少女网站：
考虑不带修：对于每次询问，把小于等于 \(x\) 的数字变成1，其他的变成0，后用数据结构维护。由于每次x不一样，对x从小到大排序，这样只需要在数据结构上进行“添加一”操作。用分块处理。添加 \(O(1)\) 查询 \(O(\sqrt{n})\)。
考虑带修：把修改按照时间分块，假设块长 \(\sqrt{n}\)，对于块内查询，只需要把最多 \(\sqrt{n}\) 个修改应用到数据结构上，然后再撤销即可。块内查询后，把整个块的所有操作永久应用到数据结构上，将数据结构重构。
还是不会
CF710F String Set Queries：
前置：AC 自动机 \(O(t)\) 时间内查询字符串 \(s\) 在 \(t\) 上出现的次数。
将添加和删除操作分离，两个不同 AC 自动机“AC+”和“AC-”。二进制分组，对于 \(2^n\) 分成不同组在添加和删除的时候在不同分组中进行，复杂度 \(O(n\log n)\)。
根号分治
每次询问给出 \(k\) 个数，求这 \(k\) 个数的一些信息。对于大于 \(\sqrt{n}\) 和小于 \(\sqrt{n}\) 的情况分开处理。
P3396 哈希冲突：对 \(p\) 进行分块，当 \(p\) 小于 \(\sqrt{n}\) 的时候预处理，大于 \(\sqrt{n}\) 的时候暴力。
P1989 无向图三元环计数：枚举每条边，看度数小的点，暴力 for 度数小的那一边。
如果一个点度数大于 \(\sqrt{m}\)，则次数不超过 \(\sqrt{m}\) 次。
如果一个点度数小于 \(\sqrt{m}\)，则次数最多做 \(m\) 次。
总复杂度 \(O(m\sqrt{m})\)。
CF444D DZY Loves Strings：一共只有 \(4n\) 个子串。把串分类成出现次数大于 \(\sqrt{(4n)}\)、小于 \(\sqrt{(4n)}\) 两类。
对于前面一类，数量很少，预处理即可。
对于后面一类，每次询问暴力 for。
其他小清新思维题
[AGC024B] Backfront：
考虑只允许放在前面怎么做。剩下的不会了
[AGC018B] Sports Festival：看起来像二分，却不是。考虑增量构造。假如一开始我们每个项目都开展的话，肯定有一个项目报名人数最多，假设这个项目是 \(x\)，有 \(k\) 个人报名显然我们的最优解至多是 \(k\) 了
考虑任意一种包含项目 \(x\) 的方案，得到的答案肯定不会比 \(k\) 更优也就是说，如果我们想得到一个优于 \(k\) 的答案，一定不能包含 \(x\) 这个项目于是我们删掉这个项目，把她当作没有，就变成了一个规模更小的子问题子问题的解法和原问题一样，所以重复这个过程就好了。
[AGC017B] Moderate Differences：？？？？？？？？？？？
标签：lfloor,12,rfloor,分块,31,sqrt,times,笔记 From： https://www.cnblogs.com/agrumestly/p/17398353.html