A 至少重复三次的数字
莫队板子。
B 小明的习题集
洛谷原题 P1494 [国家集训队] 小 Z 的袜子。
C 棋子的颜色
洛谷原题 P1903 [国家集训队] 数颜色 / 维护队列。
带修莫队：
普通莫队是二维问题，现在加上一维时间轴，做法基本上同普通莫队。
对询问 \((l,r,t)\) 排序时，第一关键字 \(pos_l\)，第二关键字 \(pos_r\)，第三关键字 \(t\)。
在时间轴上移动时，注意：
- 只有移动出现在 \([l,r]\) 才能造成贡献
- 执行过操作之后，要把操作改成撤回的样子
// u 是修改序列，q 是查询序列
void upd(int x /*当前查询操作的索引*/, int t /*当前时间*/) {
if (q[x].l <= u[t].x && u[t].x <= q[x].r) { // 在 [l, r] 内才有贡献
del(a[u[t].x]);
add(u[t].k);
}
swap(a[u[t].x], u[t].k); // 改造成撤回
}
时间复杂度
令各种东西同阶。
TODO: 一通分析
取块长 \(B = \Theta(n^{\frac 2 3})\) 可得时间复杂度 \(O(n^{\frac 5 3})\)。
D 数列分块入门-1
LOJ 原题 #6277. 数列分块入门 1
简要题意：区间加、单点查询。
分块板子。
区间加：散块暴力，整块打加法标记，\(O(\frac n B + B)\)。
单点查询：直接查，\(O(1)\)。
令 \(B \in \Theta(\sqrt n)\) 可得最优复杂度 \(O(q \sqrt n)\)。
E 数列分块入门-2
LOJ 原题 #6278. 数列分块入门 2
简要题意：区间加、区间查询 \(\sum\limits_{i=l}^r [a_i < k]\)（\(k\) 不固定，随询问给出）。
预处理：将每块内部排序。
区间查询：散块暴力，整块二分，\(O(\frac {n \log B} B + B)\)。
区间加：整块打加法标记，散块暴力后暴力重新整块排序，\(O(\frac n B + B \log B)\)。
令 \(B \in \Theta(\sqrt n)\) 可得最优复杂度 \(O(q \sqrt n \log n)\)。
区间加精细一点：散块暴力后，没加的和加过的分别是两个有序序列，归并，\(O(\frac n B + B)\)。
令 \(B \in \Theta(\sqrt {n \log n})\) 可得最优查询复杂度 \(O(q \sqrt {n \log n})\)。
据说可以用分散层叠进一步优化，但是我不会。。。