lxl

401rk8 · 2021-07-09 07:49:43 · 个人记录

题单：

lxl出过的非Ynoi题

Ynoi2008~2013

Ynoi2014~2019

由乃救爷爷

分块，整块 ST 表，散块预处理每个点到当前块左右端点的 \max；询问区间在一个块内暴力。

设块大小为 b，则分成 \frac nb 块，ST 表复杂度为 O(\frac nb\log\frac nb)，有 \frac bn 的概率询问区间在一个块内，暴力复杂度为 O(b)，总时间复杂度 O(\frac nb\log\frac nb+\frac {b^2}n)，取 b=\sqrt n 时最优，为 O(n)

大爷的字符串题

题意：每次取一个最长上升子序列，求一个区间内最少取多少次。

由于严格上升，可以转化为求区间众数的出现次数。
莫队。移动指针时除了更新每个数出现次数，还要更新每个出现次数有多少个数。

小清新人渣的本愿

莫队。bitset 维护一个数是否存在。

bitset 求区间内是否存在两数和/差为 x：

乘则直接 \sqrt n 枚举约数。

[Ynoi2016] 掉进兔子洞

普通离散化会使不同位置的相同数值映射到同一位置，丢失了个数信息。考虑魔改一下：对于数值 x（有 cnt 个），离散化后仍有 cnt 个位置，第 i 个位置表示第 i 次出现。这样就可以用 bitset 保存每个区间出现的数（且同时保留了数值和个数信息）

用莫队可以求出每次询问的三个区间出现数的 bitset，求交即可得到删去了多少数。问题在于空间无法承受，将询问分为常数组，每组莫队一次即可。时间复杂度 O(n\sqrt{3n}+\frac{n^{2}}{\omega})，空间复杂度 O(\frac{n^{2}}{3\omega})

[Ynoi2011] 初始化

发现每次都是修改全局的（y\le x），考虑对修改的倍数关系进行根号分治

• 若 x\le\sqrt{n}：使用 pre[x,i] 记录某个位置 y+kx,y\le i 加了多少（即前缀和），suf 为 y\ge i
• 若 x>\sqrt{n}：k\le\sqrt{n}，暴力枚举 y+kx

询问：

• 对于 x\le\sqrt{n}：枚举 x，以 x 分块，根据 l,r 是否在同一块用 pre,suf 简单讨论即可 O(1) 得到当前 x 的贡献 ![待补]()
• 对于 x>\sqrt{n}：有 n\sqrt{n} 次单点修改，n 次区间询问，采用分块平衡复杂度

[Ynoi2008] rrusq

离线，从小到大扫右端点，每个点在最后一次被覆盖处记入答案，这样询问就变成了后缀和

考虑加入一个矩形，使用 KDT 找到包含的点并打标记。还需要消除这些点原来的标记（在上一次覆盖处减掉），暴力做时间复杂度就是 O(n\sqrt{n})。总遍历次数实际上是 \sum 标记数 + 无标记点数，每次只会大 \sqrt{n} 个标记因此可以均摊掉，pushdown 并无影响

需要 O(n\sqrt{n}) 次单点加和 O(q) 次查询，使用分块平衡复杂度。并不卡常因此采用了 leafy 的 KDT 实现

Yuno loves sqrt technology III

预处理块 [l,r] 的众数的出现次数 ans，那么最终答案 \le ans+2\sqrt{n}。枚举左边散块的一个数 x，若出现了 ans+1 次就暴力 ++ans（预处理 x 出现的位置集合即可 O(1) 判断）；右边同理

Yuno loves sqrt technology II

区间逆序对，莫队二离板子

Yuno loves sqrt technology I

[Ynoi2015] 我回来了

[Ynoi2013] 大学

[Ynoi2016] 炸脖龙 I

[Ynoi2015] 纵使日薄西山

[Ynoi2006] rsrams

Range SubRange Absolute Mode Sum

[Ynoi2011] 成都七中

[Ynoi2010] Fusion tree

https://www.luogu.com.cn/problem/P4689