Contest

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})$。

据说可以用分散层叠进一步优化，但是我不会。。。

💡为什么取 $B \in \Theta(\sqrt {n \log n})$？

为了使时间复杂度最优，注意到区间加优于区间查询的复杂度，只要使得区间查询的 $O(\frac {n \log B} B + B)$ 最小。

即：

（用 $f(n) \approx g(n)$ 代表 $f(n) \in \Theta(g(n))$）

注意到 $\log B \approx \log n$，因此：

F 数列分块入门-3

LOJ 原题 #6279. 数列分块入门 3

简要题意：区间加、区间查询 $\max\limits_{l \le i \le r, a_i < k} a_i$（$k$ 不固定，随询问给出），若答案不存在输出 $-1$。

借用上题做法即可，查询时间复杂度 $O(q \sqrt {n \log n})$。