从零开始的 Ynoi 之旅
yuanzhiteng
·
2023-10-05 22:39:18
·
个人记录
前言
老早就听说过 Ynoi —— 由乃 OI 的大名了，里面的题都很毒瘤，当时学的太少没法做。
现在趁着退役前做做。
我是仙人掌（原 Ynoi2015 D1T1 我回来了）
题目
考察知识点：bitset，bfs 求最短路。
~~由于在一众毒瘤 $Ynoi$ 题目中太过简单，所以被踢出了 $Ynoi$ 籍。~~
适合用于入门 $Ynoi$。
看到询问多少个点的集合问题，就想到了用 $bitset$。
又由数据范围 $\sum a\le2.1\times 10^6$，显然可以直接枚举每一组 $(x_i,y_i)$。
所以现在只需要预处理出对于每个点 $u$ 到它距离 $\le d$ 的点集 $in_{u,d}$ 即可。
距离先想到求全源最短路，$Floyd\ n^3$ 的不行。
注意到所有边的边权均为 $1$，所以直接 $bfs$ 求全源最短路即可。
具体地，可以直接枚举每个点再 $bfs$ 求单源最短路，这样代码更好写。
然后就是如何统计 $in_{u,d}$。
直接暴力统计是不行的，想到用前缀思想统计。
具体地，对于点 $v$，先让 $in_{u,dis(u,v)}.set(v)$，最后前缀或 $in_{u,d}|=in_{u,d-1}$ 即可。
正确性显然。
对于查询直接枚举取并集输出 $1$ 的个数即可。
还有很坑的一点，这道题卡链式前向星。
只能 $vector$ 存图。
好像是因为 $vector$ 访问地址连续，这样速度更快。
并且图中有很多重边，在稠密图上 $vector$ 效率胜于前向星。
时间复杂度上，$bfs$ 是 $\mathcal{O}(n(n+m))$ 的，预处理出 $in_{u,d}$ 是 $\mathcal{O}(\dfrac{n^3}{\omega})$ 的，回答询问是 $\mathcal{O}(\dfrac{n\sum a}{\omega})$ 的。
总时间复杂度 $\mathcal{O}(n(n+m)+\dfrac{n^3 + n\sum a}{\omega})$。
空间复杂度上，由于最短路至多为 $\mathcal{O}(n)$ 的，所以总空间复杂度为 $\mathcal{O}(\dfrac{n^3}{\omega})$。
[code](https://www.luogu.com.cn/paste/y0ham0ui)
****
### [Ynoi2013] 无力回天
[题目](https://www.luogu.com.cn/problem/P5607)
考察知识点：线段树套线性基，树状数组，差分。
$Leval\ 1$ 级别。
拿到这道题我首先想到的就是之前做过的区间线性基。
那道题无修改操作，询问量很大，所以当时用的猫树分治做的。（具体见猫树总结）
但是这道题不一样，首先是带修，还是区间修，并且询问量并不大，才 $5\times 10^4$。
所以就不用麻烦地去离线猫树分治，直接线段树套线性基即可。
$push\_up$ 就是对左右儿子的线性基进行合并，暴力 $\mathcal{O}(\log ^2V)$ 合并即可（$V$ 是值域）。
现在考虑修改操作。
发现这个区修它就很烦，没法打 $tag$。
注意到异或的特殊性，我们利用**差分**思想。
记 $b_1=a_1,b_i=a_i \oplus a_{i-1}$。
那么不难知道 $a_i=\oplus_{i=1}^n b_i$。
所以区间修改就变成了单点修改，即 $b_l \oplus x,b_{r+1}\oplus x$。
然后考虑如何查询。
我们发现，对于 $a_{[l,r]}$，从中选取一些数字出来，总能也由 $a_l,b_{[l+1,r]}$ 的一些数字异或和给表示出来（因为每一个 $a_i$ 都能被 $a_l$ 和若干个 $b_i$ 异或得到）。
所以，**$a_{[l,r]}$ 的线性基与 $a_l,b_{[l+1,r]}$ 的线性基等价**。
因此，线段树维护 $b$ 数组，每次修改单修，查询时只需查询 $b_{[l+1,r]}$ 的线性基并将 $a_l$ 插入即可。
如何维护 $a$ 数组呢？
发现在 $b$ 上这是一个前缀问题，所以直接用树状数组即可。
修改时别忘了树状数组上也要修改。
查询时要特判 $l=r$ 的情况。
时间复杂度 $\mathcal{O}((n+m)\log n\log ^2V)$。
空间复杂度 $\mathcal{O}(n\log V)$。
[code](https://www.luogu.com.cn/paste/zc8qvr8s)
****
### [Ynoi2016] 炸脖龙 I
[题目](https://www.luogu.com.cn/problem/P3934)
考察知识点：扩展欧拉定理，树状数组。
$Level\ 1$ 级别。
做这道题前，先想到了这道题：[上帝与集合的正确用法](https://www.luogu.com.cn/problem/P4139)
对于这种幂塔取模结构，容易想到**扩展欧拉定理**，即：
$$a^b \bmod p=a^{b\bmod \varphi(p)+\varphi(p)}\bmod p(b\ge \varphi(p))$$
而又可以发现 $b \bmod \varphi(p)$ 的结构与 $a\bmod p$ 一致，所以就可以递归下去做了。
在这道题目中，即：
$$a[l]^{a[l+1]^{a[l+2]...^{a[r]}}}\equiv a[l]^{(a[l+1]^{a[l+2]...^{a[r]}}) \bmod \varphi(p)+[(a[l+1]^{a[l+2]...^{a[r]}})\ge \varphi(p)]\varphi(p)}(\bmod p)$$
直接可以递归下去做，边界为 $p=1$，直接返回 $0$；$l=r$，直接返回 $a[l]\bmod p$。
恶心的地方在于对 $a[l+1]^{a[l+2]...^{a[r]}}\ge \varphi(p)$ 的特判。
具体地，可以用结构体 $\{val,flag\}$ 存储返回值。
$val$ 存值，$flag$ 判断是否 $\ge mod$。
在递归函数中需要特判返回值 $val$ 与模数 $p$ 的关系更新 $flag$。
同时在快速幂中也需要如此。
具体实现看代码。
至于区间修改操作，用树状数组维护序列即可。
时间复杂度上，$p\to \varphi(p)\to \varphi(\varphi(p))\cdots$ 这样的迭代**至多只会进行 $\mathcal{O}(\log p)$** 次。
每一层有 $\mathcal{O}(\log n)$ 的树状数组查询以及 $\mathcal{O}(\log p)$ 的快速幂。
加上预处理线性筛欧拉函数 $\mathcal{O}(p)$。
因此总时间复杂度为 $\mathcal{O}(p+\log p(\log n+\log p))$。
[code](https://www.luogu.com.cn/paste/9diz50j9)
****
### [Ynoi2009] rprsvq
[题目](https://www.luogu.com.cn/problem/P6108)
考察知识点：大力推式子，组合恒等式，线段树。
$Level\ 2$ 级别。
难度全在推式子上，代码很好写。
独立做出来的。
我们先考虑对于数列 $\{a_n\}$ 的方差如何求：
$$\begin{aligned}
S&=\dfrac{1}{n}\sum_{i=1}^n(a_i-\bar{a}^2)\\
&=\dfrac{1}{n}\sum_{i=1}^n(a_i^2+\bar{a}^2-2a_i\bar{a})\\
&=\dfrac{1}{n}(\sum_{i=1}^na_i^2+\sum_{i=1}^n\bar{a}^2-\sum_{i=1}^n2a_i\bar{a})\\
&=\dfrac{1}{n}(\sum_{i=1}^na_i^2+\sum_{i=1}^n(\dfrac{1}{n}\sum_{j=1}^na_j)^2-\sum_{i=1}^n2a_i(\dfrac{1}{n}\sum_{j=1}^na_j))\\
&=\dfrac{1}{n}(\sum_{i=1}^na_i^2+n(\dfrac{1}{n}\sum_{j=1}^na_j)^2-\dfrac{2}{n}\sum_{i=1}^na_i\sum_{j=1}^na_j)\\
&=\dfrac{1}{n}(\sum_{i=1}^na_i^2+\dfrac{1}{n}(\sum_{i=1}^na_i)^2-\dfrac{2}{n}(\sum_{i=1}^na_i)^2)\\
&=\dfrac{1}{n}(\sum_{i=1}^na_i^2-\dfrac{1}{n}(\sum_{i=1}^na_i)^2)
\end{aligned}$$
然后这个东西可以拆成两部分用线段树维护：
对于 $\sum_{i=1}^na_i$，直接维护区间和，不用多说。
对于 $\sum_{i=1}^na_i^2$，即要维护区间平方和，考虑到：
$$\sum_{i=1}^n(a_i+x)^2=\sum_{i=1}^na_i^2+2x\sum_{i=1}^na_i+nx^2$$
而 $\sum_{i=1}^na_i$ 是可以知道的，所以对于区间加操作也能维护，即：
$$\Delta=2xsum+(r-l+1)x^2$$
接下来考虑如何维护所有子序列的方差之和。
为了方便，以下统一将下标改为 $[1,n]$，其中 $n=r-l+1$。
显然不能直接将每个子序列的方差求出来求和，考虑能不能整体贡献。
上面的单个序列的方差式子告诉我们只需要知道所有子序列的 $\dfrac{1}{len}(\sum a_i^2-\dfrac{1}{len}(\sum a_i)^2)$。
这个东西直接不好处理，于是想到枚举子序列的长度 $k$，这样前面的 $\dfrac{1}{len}$ 就能很自然地合并在一起。
接下来只需要考虑所有长度为 $k$ 的子序列的 $\sum a_i^2-\dfrac{1}{len}(\sum a_i)^2$ 之和。
前面那一项 $\sum a_i^2$ 很好思考。
计算每一项带来的贡献，在该项必选情况下剩余的 $n-1$ 项中还要选 $k-1$ 项，方案数为 $C_{n-1}^{k-1}$。
故总贡献为 $C_{n-1}^{k-1}\sum_{i=1}^na_i^2$。
再考虑后面那一项。
不好思考，干脆直接找规律：
对于 $\{a_1,a_2,a_3,a_4\}$：
若 $k=2$，则有：
$$\begin{aligned}
(a_1+a_2)^2+(a_1+a_3)^2+(a_1+a_4)^2+(a_2+a_3)^2+(a_2+a_4)^2+(a_3+a_4)^2&=3(a_1^2+a_2^2+a_3^2+a_4^2)+2(a_1a_2+a_1a_3+a_1a_4+a_2a_3+a_2a_4+a_3a_4)\\
&=3(a_1^2+a_2^2+a_3^2+a_4^2)+(a_1a_2+a_1a_3+a_1a_4+a_2a_1+a_2a_3+a_2a_4+a_3a_1+a_3a_2+a_3a_4)\\
&=3(a_1^2+a_2^2+a_3^2+a_4^2)+(a_1(a_2+a_3+a_4)+a_2(a_1+a_3+a_4)+a_3(a_1+a_2+a_4)+a_4(a_1+a_2+a_3))\\
&=3\sum_{i=1}^4a_i^2+\sum_{i=1}^4a_i(-a_i+\sum_{j=1}^4a_j)
\end{aligned}$$
若 $k=3$，同理可得和为：
$$3\sum_{i=1}^4a_i^2+2\sum_{i=1}^4a_i(-a_i+\sum_{j=1}^4a_j)$$
发现形式都很相像，都是 $A\sum_{i=1}^na_i^2+B\sum_{i=1}^na_i(-a_i+\sum_{j=1}^na_j)$ 的形式。
接下来思考这个系数 $A,B$ 具体为多少。
对于前一个系数，令该项必选，剩余 $n-1$ 项中选 $k-1$ 项，因此 $A=C_{n-1}^{k-1}$。
对于后一个系数，实际上是所有的两两相乘方案数，令该两项必选，剩余 $n-2$ 项中选 $k-2$ 项，因此 $B=C_{n-2}^{k-2}$。
故后面这一项的总贡献为 $C_{n-1}^{k-1}\sum_{i=1}^na_i^2+C_{n-2}^{k-2}\sum_{i=1}^na_i(-a_i+\sum_{j=1}^na_j)$。
（第一遍推的时候就是系数 $B$ 漏乘了个组合数，导致后面出错重推，引以为戒）
将上面两个式子通通带入原式，我们便能得到答案的表达式（注意区分 $n$ 和 $k$，想清楚再下笔）：
$$Ans=\sum_{k=1}^n\dfrac{1}{k}(\ C_{n-1}^{k-1}\sum_{i=1}^na_i^2 - \dfrac{1}{k}(\ C_{n-1}^{k-1}\sum_{i=1}^na_i^2+C_{n-2}^{k-2}\sum_{i=1}^na_i(-a_i+\sum_{j=1}^na_j) \ ) \ )$$
看着就很恶心 $\cdots
直接计算是 \mathcal{O}(n^2) 的，所以接下来就是漫长的化简过程了。
需要用到的式子：组合恒等式之吸收式 C_{n-1}^{k-1}=\dfrac{k}{n}C_{n}^k；二项式定理的应用 \sum_{i=0}^nC_n^i=2^n
开始化简：
Ans&=\sum_{k=1}^n\dfrac{1}{k}(\ C_{n-1}^{k-1}\sum_{i=1}^na_i^2 - \dfrac{1}{k}(\ C_{n-1}^{k-1}\sum_{i=1}^na_i^2+C_{n-2}^{k-2}\sum_{i=1}^na_i(-a_i+\sum_{j=1}^na_j) \ ) \ )\\
&=\sum_{k=1}^n\dfrac{1}{k}(\ \dfrac{k-1}{k}C_{n-1}^{k-1}\sum_{i=1}^na_i^2 - \dfrac{1}{k}C_{n-2}^{k-2}\sum_{i=1}^na_i(-a_i+\sum_{j=1}^na_j) \ )\\
&=\sum_{k=1}^n\dfrac{1}{k}(\ \dfrac{k-1}{k}C_{n-1}^{k-1}\sum_{i=1}^na_i^2 + \dfrac{1}{k}C_{n-2}^{k-2}\sum_{i=1}^na_i^2-\dfrac{1}{k}C_{n-2}^{k-2}\sum_{i=1}^na_i\sum_{j=1}^na_j) \ )\\
&=\sum_{k=1}^n(\ \dfrac{k-1}{k^2}C_{n-1}^{k-1}\sum_{i=1}^na_i^2 + \dfrac{1}{k^2}C_{n-2}^{k-2}\sum_{i=1}^na_i^2-\dfrac{1}{k^2}C_{n-2}^{k-2}(\sum_{i=1}^na_i)^2 \ ) \\
&=\sum_{k=1}^n(\ \dfrac{k-1}{k^2}\cdot \dfrac{k}{n} C_{n}^{k}\sum_{i=1}^na_i^2 + \dfrac{1}{k^2}\cdot \dfrac{k-1}{n-1}\cdot\dfrac{k}{n}C_{n}^{k}\sum_{i=1}^na_i^2-\dfrac{1}{k^2}\cdot \dfrac{k-1}{n-1}\cdot\dfrac{k}{n}C_{n}^{k}(\sum_{i=1}^na_i)^2 \ )\\
&=\sum_{k=1}^n(\ \dfrac{1}{n}\cdot \dfrac{k-1}{k} C_{n}^{k}\sum_{i=1}^na_i^2 + \dfrac{1}{n(n-1)}\cdot \dfrac{k-1}{k}C_{n}^{k}(\sum_{i=1}^na_i^2-(\sum_{i=1}^na_i)^2) \ )\\
&=\sum_{k=1}^n(\ \dfrac{1}{n}(1-\dfrac{1}{k}) C_{n}^{k}\sum_{i=1}^na_i^2 + \dfrac{1}{n(n-1)}(1-\dfrac{1}{k})C_{n}^{k}(\sum_{i=1}^na_i^2-(\sum_{i=1}^na_i)^2) \ )\\
&=\dfrac{1}{n}\sum_{i=1}^na_i^2(\sum_{k=1}^n C_n^k-\sum_{k=1}^n\dfrac{C_n^k}{k})+\dfrac{1}{n(n-1)}(\sum_{i=1}^na_i^2-(\sum_{i=1}^n a_i)^2)(\sum_{k=1}^nC_n^k-\sum_{k=1}^n\dfrac{C_n^k}{k})\\
&=\dfrac{1}{n}\sum_{i=1}^na_i^2(2^n-1-\sum_{k=1}^n\dfrac{C_n^k}{k})+\dfrac{1}{n(n-1)}(2^n-1-\sum_{k=1}^n\dfrac{C_n^k}{k})(\sum_{i=1}^na_i^2-(\sum_{i=1}^n a_i)^2)\\
&=\dfrac{2^n-1-\sum_{k=1}^n\dfrac{C_n^k}{k}}{n}\sum_{i=1}^na_i^2+\dfrac{2^n-1-\sum_{k=1}^n\dfrac{C_n^k}{k}}{n(n-1)}(\sum_{i=1}^na_i^2-(\sum_{i=1}^n a_i)^2)
\end{aligned}
真麻烦。
推导到这里会发现 \sum_{i=1}^na_i^2 和 \sum_{i=1}^n a_i 都能用线段树去维护，可以做到单次 \mathcal{O}(\log n) 的回答。
所以关键在于对 \sum_{k=1}^n\dfrac{C_n^k}{k} 的处理了。
肯定不能每次回答都现算，这样总查询复杂度会是 \mathcal{O}(qn) 的，无法通过。
怎么办呢？
记 f(n)=\sum_{k=1}^n\dfrac{C_n^k}{k}，考虑如何能在线性时间内预处理出 f(1) ~ f(n)。
也就是说看能不能找到 f 的线性递推式。
这个就有点难搞了，卡了好久，可以通过有理积分去算，这里提供一种巧妙的组合运算方法：
需要用到的式子：帕斯卡公式 C_n^k=C_{n-1}^k+C_{n-1}^{k-1} 以及上面提到的组合恒等式之吸收式和二项式定理的应用。
f(n)-f(n-1)&=\sum_{k=1}^n\dfrac{C_n^k}{k}-\sum_{k=1}^{n-1}\dfrac{C_{n-1}^k}{k}\\
&=\dfrac{1}{n}+\sum_{k=1}^{n-1}\dfrac{C_n^k}{k}-\sum_{k=1}^{n-1}\dfrac{C_{n-1}^k}{k}\\
&=\dfrac{1}{n}+\sum_{k=1}^{n-1}\dfrac{C_n^k-C_{n-1}^k}{k}\\
&=\dfrac{1}{n}+\sum_{k=1}^{n-1}\dfrac{C_{n-1}^{k-1}}{k}\\
&=\dfrac{1}{n}+\sum_{k=1}^{n-1}\dfrac{\dfrac{k}{n}C_{n}^{k}}{k}\\
&=\dfrac{1}{n}+\dfrac{1}{n}\sum_{k=1}^{n-1}C_{n}^{k}\\
&=\dfrac{1+\sum_{k=1}^{n-1}C_{n}^{k}}{n}\\
&=\dfrac{1+\sum_{k=0}^{n}C_{n}^{k}-C_n^0-C_n^n}{n}\\
&=\dfrac{\sum_{k=0}^{n}C_{n}^{k}-1}{n}\\
&=\dfrac{2^n-1}{n}
\end{aligned}
即：
f(n)=f(n-1)+\dfrac{2^n-1}{n}
这样我们便能 \mathcal{O}(n) 线性递推 f 了（准确地说，如果逆元现算的话应该是 \mathcal{O}(n\log p) 的）。
预处理出 2 的次幂以及 f，那么答案为：
Ans=\dfrac{2^n-1-f(n)}{n}\sum_{i=1}^na_i^2+\dfrac{2^n-1-f(n)}{n(n-1)}(\sum_{i=1}^na_i^2-(\sum_{i=1}^n a_i)^2)
线段树维护区间和，区间平方和，支持区间加即可。
注意代码中不要全开 long\ long，会 MLE，开 int，计算途中强制转换成 long\ long 即可。
同时别忘了处处取模（我刚开始就是因为一个很小的地方没取模 WA 了老半天）。
时间复杂度 \mathcal{O}(n\log p+m\log n)。
code
[Ynoi2017] 由乃的 OJ
题目
考察知识点：位运算，贪心，线段树。
是一道好题。
做这道题前，先看这道题：[[NOI2014] 起床困难综合症](https://www.luogu.com.cn/problem/P2114)
乍一看，运算符有三个 $\&,|,\oplus$，手玩后发现三者之间并没有结合律。
也就是说，它们间的顺序不能改变。
那怎么办？
注意到这三种运算符的特殊性：位运算，且均不会产生进位。
所以不难想到**对每一位拆开考虑**。
二进制下，每一位上只可能是 $0/1$。
所以我们令 $a_0=(000\cdots 000)_2,a_1 = (111\cdots 111)_2$。
然后我们直接顺序线性扫一遍运算，得到 $a_0,a_1$ 运算后最终的结果。
此时的 $a_0,a_1$ 就有特殊含义了：
**对于 $a_0$ 二进制下的第 $i$ 位的值即为初始值 $x$ 的第 $i$ 位为 $0$ 的情况下经过运算后最终的值；**
**类似地，对于 $a_1$ 二进制下的第 $i$ 位的值即为初始值 $x$ 的第 $i$ 位为 $1$ 的情况下经过运算后最终的值。**
知道这些后，我们就能统计答案了。
为了使答案尽可能大，我们贪心地从高位向低位枚举每一位。
若 $a_0[i]=1$，我们就选上这一位，$ans|=1ll< 若 $a_1[i]=1$ 并且 $1ll< 最后的 $ans$ 即为最终答案。 时间复杂度 $\mathcal{O}(n)$。 然后我们来看看这道题。 你会发现其实是刚才那道题的树上带修多组查询的版本。 树上问题想到用树链剖分转换成区间问题。 带修的区间问题想到用线段树去维护。 如果我们枚举每个位暴力合并两个子区间，时间无法承受。 所以现在的关键在于如何 $\mathcal{O}(1)$ 地去合并两个子区间，即怎么写 $push\_up$ 函数。 还是利用位运算的性质，即**各个位值间的运算互不干扰**。 所以我们就像 $bitset$ 那样，不用一个一个位值合并，直接整体合并。 我们记 $f_0,f_1$ 的第 $i$ 位分别表示初始值的第 $i$ 位为 $0/1$ 时从左到右经过该区间后的值，$g_0,g_1$ 为从右往左。 那么就不难写出合并函数了： $$p.f_0=(l.f_0\ \&\ r.f_1)\ |\ (\sim l.f_0\ \&\ r.f_0)$$ $$p.f_1=(l.f_1\ \&\ r.f_1)\ |\ (\sim l.f_1\ \&\ r.f_0)$$ $$p.g_0=(r.g_0\ \&\ l.g_1)\ |\ (\sim r.g_0\ \&\ l.g_0)$$ $$p.g_1=(r.g_1\ \&\ l.g_1)\ |\ (\sim r.g_1\ \&\ l.g_0)$$ 其中 $\sim$ 表示按位取反。 非常巧妙地解决了这个问题。 为什么要将从左往右和从右往左分开算呢？ 首先容易知道两者的结果是不一样的。 至于为什么要都维护，树链查询时你就知道了，下面会说。 接下来就是树剖了。 唯一需要注意的就是如何去查询。 由于上面也说了，顺序对于答案是会有影响的。 为了不出错，我们这样来做： 将 $u\to v$ 拆成两段 $u\to lca,lca\to v$。 对于每一段，先不要急着合并，不然是错的，拿两个结构体 $ans1,ans2$ 分别存下来。 然后我们发现，线段树上查询出来的区间在树上深度越小下标越小。 对于 $u\to lca$，我们不断经过的是线段树上 $r\to l$，而从 $lca\to v$，我们不断经过的是 $l\to r$。 因此，我们需要 $swap(ans1_i.f_0,ans1_i.g0),swap(ans1_i.f_1,ans2_i.g_1)$。 这样再合并就没问题了。 合并时先从 $u\to lca$ 按序合并 $ans1$ 中的值，再从 $lca\to v$ 按序合并 $ans2$ 中的值。 最后对于查询出来的 $a_0,a_1$ 贪心统计答案即可。 实现时，需要注意的是初始化问题，特别是对于 $f_0,f_1,g_0,g_1$，$\{0,0\}$ 并不是其空值，所以对于 $f_0/f_1/g_0/g_1$ 其为空（未被更新过）时需要特殊处理直接赋值。 代码实现上的细节还蛮多的，具体就见代码吧。 时间复杂度 $\mathcal{O(q\log^2 n)}$。 [code](https://www.luogu.com.cn/paste/hza694ml) **** ### [Ynoi2016] 掉进兔子洞 [题目](https://www.luogu.com.cn/problem/P4688) 考察知识点：莫队配合 $bitset$，离散化技巧，其它奇淫技巧。 $Level\ 2$ 级别。 看到题目中的操作，先往树状数组扫描线（$HH$ 的项链）的方向想。 但很显然不行，因为没法做到对三个区间进行去重。 但别忘了 $HH$ 的项链这道题还可以莫队做。 一看范围 $10^5$，可以离线，直接上**莫队**维护这种颜色种类的问题。 接下来的问题就在于如何对三个区间进行去重。 不难发现去掉的元素是三个区间中的公共元素。 公共元素即三个区间元素的交集，集合间的运算又想到了用 $bitset$ 来优化。 但是元素出现个数不一定为 $0/1$ 关系，好像不能用 $bitset$？ 这个就是个小技巧了： 首先将序列离散化。 但是与一般的离散化不一样的是，我们将离散化后的值变为**小于等于该元素的数的个数**。 那么离散化后**两个相邻元素 $x_1,x_2$ 的差即为 $x_2$ 在原序列中出现的个数**。 我们利用这个性质来进行 $bitset$ 的修改。 具体地，在进行莫队时，如果当前要加入 $x$ 的贡献，假设先前 $x$ 已经出现了 $cnt_x$ 次，那么我们就将 $bitset$ 中 $a[x]-cnt_x$ 处设为 $1$，再 $cnt_x++$。 减去贡献同理，注意一下修改顺序即可。 最后每一组的询问就是三个区间对应的 $bitset$ 的交集大小。 为什么这样是对的呢？ 首先由上面的分析，对于某一种颜色的修改只会是 $bitset$ 上某一段连续的区间。 并且修改并不会修改到别的元素去。 也就是说，**我们对每一种颜色都在 $bitset$ 上开了一段连续的区间**。 取交集就是在对每一种颜色分别取 $\min$。 很神奇地解决了这个问题。 完了吗？ 再看一眼数据范围：$m\le 10^5$。 我们要对每一组询问都开 $n=10^5$ 大小的 $bitset$，那么总的空间就会有 $\dfrac{10^5\times 10^5 \times 4}{1024\times 1024\times 32}=1192\ MB$，开不下！ 怎么办，难道还是不行吗？ 这就要用到奇淫技巧了。 **我们将询问拆成三组，每组都跑一次莫队**。 这样 $m$ 降为了 $\lceil \dfrac{10^5}{3}\rceil=33334$，空间降到了$ \dfrac{10^5\times 33334 \times 4}{1024\times 1024\times 32}=398\ MB$，可以通过本题。 时间复杂度 $\mathcal{O}(n\sqrt{n})$。 [code](https://www.luogu.com.cn/paste/9pcmx0j1) **** ### [Ynoi2015] 盼君勿忘 [题目](https://www.luogu.com.cn/problem/P5072) 考察知识点：转换，莫队，根号分治，光速幂，卡常。 $Level\ 2$ 级别。 可以学到很多卡常小技巧。 对于一个区间的所有**子序列（不是子区间）** 的去重和，肯定不能枚举。 与上面 rprsvq 一题思路相像，考虑每个数的贡献。 假设当前区间长度为 $len$，对于数 $x$ 它的出现次数为 $k$，那么该数对当前区间的贡献应为： $$(2^{len}-2^{len-k})x$$ 本质上就是容斥，用总的方案数减去一个 $x$ 都不选的方案数达到去重的目的。 不带修，并且知道单个数字的贡献，可以离线，强烈暗示用莫队。 但是发现一个问题，当区间长度在变化的时候，$len$ 变了单个数的贡献也就随之发生了变化。 如果直接枚举每个数那么单个询问就是 $\mathcal{O}(n)$ 的，而我们最多只能容许 $\mathcal{O}(\sqrt{n})$ 的回答，这样总的复杂度才是 $\mathcal{O}(m\sqrt{n})$ 的才能接受。 既然直接枚举每个数不行，那么我们可以枚举出现次数。 具体地，我们可以记录出现次数为 $x$ 的数的和 $sum_x$，莫队过程中很好维护，那么当前出现次数的所有数的贡献就应该是 $(2^{len}-2^{len-x})sum_x$。 如果直接枚举出现次数的话好像还是 $\mathcal{O}(n)$ 的，没法通过。 其实可以优化，用双向链表支持插入删除即可达到 $\mathcal{O}(\sqrt{n})$。 但是我懒得写，所以考虑另外一种根号分治的做法。 上面我们得到了两种统计方法，我们试着用这两种方法去平衡复杂度。 **我们对出现次数根号分治**。 对于出现次数 $\le \sqrt{n}$ 的数，我们使用法一，统计 $sum_x$。 对于出现次数 $>\sqrt{n}$ 的数，我们使用法二，统计这些数中每个数的出现次数。 来看看复杂度对不对。 对于前者，统计答案时直接枚举出现次数，是 $\mathcal{O}(\sqrt{n})$ 的。 对于后者，出现次数 $>\sqrt{n}$ 的数总共不会超过 $\mathcal{O}(\sqrt{n})$ 个，直接枚举这些数，也是 $\mathcal{O}(\sqrt{n})$ 的。 总的时间复杂度就是 $\mathcal{O}(m\sqrt{n})$ 的了，可以通过。 具体实现时，可以预先处理出整个序列中出现次数 $>\sqrt{n}$ 的数并打上标记存入数组中，这样在莫队中就可以分类处理 $\le \sqrt{n}$ 和 $>\sqrt{n}$ 的了。 完了。 真的完了吗？ 交上去 $T$ 一片。 仔细分析复杂度，发现由于模数不同无法预处理，所以在统计答案时快速幂还有一个 $\log$！ 那复杂度就退化为了 $\mathcal{O}(m\sqrt{n}\log p)$，无法通过。 那怎么办，对于每个询问，我们最多只能容许 $\mathcal{O}(\sqrt{n})$ 的运算。 哎，等等，$\mathcal{O}(\sqrt{n})$ 预处理，$\mathcal{O}(1)$ 询问 $\cdots 这不就是光速幂吗！ 由于底数固定，所以可以用光速幂。 具体地，我们 \mathcal{O}(\sqrt{n}) 预处理出： pow1:2^0,2^1,\cdots ,2^{\sqrt{n}} pow2:2^{\sqrt{n}},2^{2\sqrt{n}},\cdots ,2^{\sqrt{n}\times\sqrt{n}} 这里的 \sqrt{n} 都是下取整。 这样我们便能 \mathcal{O}(1) 回答询问了： 2^k=qpow1[k\bmod \sqrt{n}]\times qpow2[\lfloor \dfrac{k}{\sqrt{n}} \rfloor] 相当于 qpow1 存余数，qpow2 存商，利用根号达到平衡复杂度的目的。 这样时间复杂度就正确了，\mathcal{O}(m\sqrt{n})。 但是人傻常数大，交上去 T 了 6 个点。 考虑怎么卡常吧。 首先对于函数中传 mod 类型改成常量引用，这样更快。 然后调整块长，并将语言改成 c++98 不开 O2，只 T 了两个点。 （似乎 c++14 开了 O2 情况下取模运算很慢） 然后怎么样都过不了这两个点。 复杂度假了？不是的。 关键在于途中大量的取模运算，而取模运算又比较慢，导致常数巨大。 于是想办法避免取模。 直接开 \_\_int128（编译器中的 \_\_int128\_t 也是）。 这样中途对 ans 就不用取模（光速幂的预处理还是需要取模的），最后统一取模即可。 注意要手写快读快写。 交上去原先跑了 3s 多过不了的两个点都只跑了 1s 左右，快了将近一倍，取模常数真恐怖。 时间复杂度 \mathcal{O}(m\sqrt{n})。 code [Ynoi2015] 我回来了 题目 考察知识点：转换，思维，线段树，树状数组，二维偏序。 挺有意思的一道题。 而且我发现这道题之前居然被拿来出在了高一高二联合 $NOI$ 模拟赛的 $T1$。 代码及其简单，而思维难度却不低。 我们先不考虑对于 $[L,R]$ 区间的查询，考虑对于某一个 $d$ 的答案。 我们发现，实际上起作用的区间应为： $$[1,d],[d+1,2d],[2d+1,3d],\cdots,[\lfloor \dfrac{n}{d} \rfloor d + 1,n]$$ 那么对于所有的 $d\in[1,n]$，总区间个数是 $\sum_{d=1}^n \lceil \dfrac{n}{d} \rceil =\mathcal{O}(n\log n)$ 的（调和级数）。 只有当某个区间里有对应血量的随从时才能取，$d$ 的答案即为最长的前缀可取区间个数$+1$（$+1$ 是因为最后还有一次亵渎）。 设 $g_{d,i}$ 表示 $d$ 的最早第多少次操作 $d$ 的最长前缀可取区间能够达到 $i$。 想办法求出 $g_{d,i}$。 设 $f_{d,i}$ 表示 $d$ 的第 $i$ 个区间最早第几次操作有随从出现。 那么不难得知： $$g_{d,i}=\max\{g_{d,i-1},f_{d,i}\}$$ 为什么是 $Max$ 呢？因为需要二者皆成立时才行。 也就是说，需要前 $i-1$ 个区间都能取到，并且第 $i$ 个区间也能取到。 这个就是个前缀最大值，很好处理。 枚举每个区间求一遍前缀最大值，$\mathcal{O}(n\log n)$。 然后考虑怎么求 $f_{d,i}$。 这个就很简单了，设 $a_i$ 为血量为 $i$ 的随从最早第几次操作出现。 那么： $$f_{d,i}=\min_{(i-1)d+1\le j\le \min(id,n)}\{a_j\}$$ 发现这是个区间最小值。 所以将操作离线，提前预处理出 $a_i$，就能用线段树维护 $f_{d,i}$ 了。 这一部分枚举每个区间，再线段树查询，复杂度是 $\mathcal{O}(n\log ^2n)$ 的。 最后考虑如何查询 $[L,R]$ 的答案。 我们发现，对于 $g_{d,i}=k$ 的所有 $d$，**均会在 $\ge k$ 的询问操作且包含了 $d$ 的询问操作中产生 $1$ 的贡献**。 这显然是个二维偏序问题。（操作编号，$d$） 所以我们将相同的 $g_{d,i}$ 放在一个 $vector:\ v[g_{d,i}].push\_back(d)$ ，从前往后枚举每个操作 $i$，将当前 $v[i]$ 中的所有 $d$ 在树状数组上 $+1$。 然后查询直接查树状数组上 $[L,R]$ 的和即可。 具体实现时，可以不用将 $f,g$ 开出来，直接枚举区间进行一系列查询更新求出 $g$ 并将其存入对应的 $vector$ 中即可。 最后的答案别忘了还要加上 $r-l+1$（因为最后还有一次亵渎）。 时间复杂度 $\mathcal{O}(n\log^2n+m\log n)$。 [code](https://www.luogu.com.cn/paste/qv17uvph)