Ynoi总结 - 洛谷保存站

# Ynoi总结

做的不是很多，主要是熟悉根号复杂度算法及其数据结构，提升一点DS水平。

### [P7446 [Ynoi2007] rfplca](https://www.luogu.com.cn/problem/P7446)

考虑分块，然后对每个点维护父亲 $f_i$ 和跳出块外的第一个祖先 $p_i$。

注意到一个块如果被整体修改 $\sqrt n$  次，那么里面所有点的$f_i=p_i$，这样就可以直接在块上打标记了。

然后就做完了，时间复杂度$O(n\sqrt n)$。

细节就是散块修改要把整个块全部重构，lca写成暴力的样子。

### [P5072 [Ynoi2015] 盼君勿忘](https://www.luogu.com.cn/problem/P5072)

**[__harp](https://www.luogu.com.cn/user/574167)** 秒了，还是太菜了。

显然可以注意到，假如一个数 $c$ 出现 $x$ 次，那么它的贡献是 $(2^{len}-2^{len-x})\times c$

看到$5\times 10^5$ 不开 1s 猜测是 $O(n\sqrt n)$的。

考虑怎么做，前面的式子可以光速幂维护(每次询问处理 2 的 1~$\sqrt n$次方和( 1~$\sqrt n$倍的$\sqrt n$)次方)

后面的式子好像只能暴力维护，于是考虑根号分治+莫队。

1. 对于 $x\le \sqrt n$ 的开桶记录这些 $c$ 的和然后一起做

2. 对于 $x\ge \sqrt n$ 的只有不到$\sqrt n$个数，把序列中出现超过$\sqrt n$的数记录下来每次暴力判断即可（可以用链表）。

然后你用莫队维护一下每个数出现次数就行了，时间复杂度$O(n\sqrt n)$，一点细节没有。

### [P10149 [Ynoi1999] XM66F](https://www.luogu.com.cn/problem/P10149)

~~家训容斥~~

这里以加入右端点为例子，左端点就相当于倒过来。

记 $r_i$ 表示 $\sum ^i_{j=1}[a_j\le a_i]\\$

那么我们加入端点 $R$ 的贡献就是 $\sum ^{R-1}_{i=l}[a_i=a_R](r_R-r_i)\\$

然后你发现这个东西开两个桶随便维护，就做完了。

维护 $r_i$ 用树状数组

时间复杂度 $O(n\sqrt n)$。

### [P5527 [Ynoi2012] NOIP2016 人生巅峰](https://www.luogu.com.cn/problem/P5527)

考虑一个长为 $len$ 的区间，那么它能选出的集合数量为$2^{len}-1$，这个区间可能产生的不同总贡献个数最多为 $1000len$ 。

根据抽屉原理，如果 $2^{len}-1>1000len$ 那么答案必然是 `Yuno`

否则 $len \le 13$，那么直接$2^{len}$枚举每个集合，判断这个和是否出现过，转移和用$s_{i}=s_{i\oplus \text{lowbit(i)}}+ v[\log \text{lowbit(i)}]$

这样时间复杂度为$O(q\times 2^{13})$,但是显然重复的比较多所以跑的飞快。

应该还有单次询问$O(\frac{13v}{\omega})$的 bitset 优化 dp 做法

### [P5311 [Ynoi2011] 成都七中](https://www.luogu.com.cn/problem/P5311)

感觉这题好像只能暴力，所以考虑点分治。

我们把询问挂在节点上，然后考虑第一个能只经过 $[l,r]$ 中的点能到达该点的点分中心。

那么这个询问当且仅当在这次点分里面找答案是对的，因为不可能经过上一个点分中心。

对于一个点分中心，我们把所有询问 $(l,r)$ 拿出来，还有从点分中心到每个点的路径上的最大最小值和它的颜色 $(c_x,mn,mx)$。

那么对于一个询问，一个点可能能贡献到该点当且仅当 $l\le mn,mx\le r$,二维偏序板题，排序 $r$ 树状数组 $l$。

颜色的话，考虑只保留 $mn$ 最大那个。

时间复杂度$O(n\log^2 n)$。

### [P11620 [Ynoi Easy Round 2025] TEST_34](https://www.luogu.com.cn/problem/P11620)

发现 $opt=2$ 就是线性基乱维护，那么考虑线段树维护线性基。

但是区间修改维护不了一点，于是想办法把区间修改变成单点修改。

差分启动！设 $b_i=a_i\oplus a_{i-1}$,那么 $a_l,a_{l+1}\cdots a_r$ 组成的线性基与 $a_l,b_{l+1}\cdots b_r$ 效果相同，因为你显然可以通过后面的线性基异或出前面的所有数。

再写个树状数组维护 $a_i$ ($b_i$ 的前缀异或和)就行了，时间复杂度的话，线性基合并是 $O(\log^2V)$ 的，但是全位运算常数不太大。

总的时间复杂度是 $O(m\log n\log ^2V)$。

### [P5524 [Ynoi2012] NOIP2015 充满了希望](https://www.luogu.com.cn/problem/P5524)

考虑用线段树维护每个点 2 操作的时间戳。

1 操作两个单点修改

2 操作一个区间修改

3 操作记录时间戳 $t_i$

为什么维护时间戳？因为知道时间戳也可以知道对应值，并且便于判断这个值得到的时间是否在询问区间内。

考虑扫描 $r$，每次对于一个 3 操作，将树状数组中 $t_i$ 位置加 $v_{t_i}$,询问就询问树状数组中区间 $[l,r]$ 的值，也就是在 $l$ 后的 2 操作能影响到的询问。

时间复杂度 $O((m+q)\log n)$,写个快读就过了。

### [P4117 [Ynoi2018] 五彩斑斓的世界](https://www.luogu.com.cn/problem/P4117)

第二分块。

首先考虑分块，发现我们块内的最大值单调不增。

考虑我们让每个块都能在 $O(1)$ 的时间内将最大值减小 1，这样时间复杂度就是 $O(V)$ 的。

首先考虑合并两种数，你发现并查集就可以了，顺便维护一下 size。

修改：

如果 $mx\le 2\cdot x$，那么暴力将 $[x,mx]$ 内的数往下合并。

如果 $mx>2\cdot x$，那么暴力将 $[1,x]$ 内的数向上合并，打个区间减标记。

这样显然复杂度是 $O(V)$ 的，总时间复杂度 $O(V\sqrt n)$。

注意到你空间开不下 $O(V\sqrt n)$ 空间，于是考虑逐块处理，对每个块枚举所有询问，这样空间 $O(V)$，可以过了。

写了一辈子。

### [P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I](https://www.luogu.com.cn/problem/P5046)

杂题讲了个这道题的强化版，于是补了一下。

考虑分块，块内贡献带 $\log$ 处理一下就行了，然后处理块内到块外每个位置的贡献及其前缀和。

那么整块对整块，整块对散块都可以用这个前缀和处理，考虑散块对散块如何 $O(\sqrt n)$

考虑求逆序对的方法：

1.树状数组，肯定带 $\log $，不行

2.归并排序。

那你先把每个块排好序，然后把两个块归并一下就好了

时间复杂度 $O(n\sqrt n)$。

### [P5065 [Ynoi2014] 不归之人与望眼欲穿的人们](https://www.luogu.com.cn/problem/P5065)

模拟赛T2。

首先有经典结论：以一个点为左端点的本质不同的或和只有 $O(\log V)$ 种。

先分块，每个块内处理一个 $s_i$ 表示长度为 $i$ 的区间的最大或和，这个直接维护 30 个指针表示该位上一个 1 的位置就行了。

然后再处理前缀后缀本质不同的 $\log V$ 个或和。

考虑计算答案，首先是块内的，这个直接先查最大值然后二分查找即可。

如果一个块内的或和无法达到，那么考虑跨块的答案，枚举一个块作为终点，块内的 $\log V$ 个前缀都可以作为终点，我们动态维护从该块起点往前的 $\log V$ 个不同的值，然后双指针就可以了，双指针完了之后再把当前块的 $\log V$ 个后缀合并再去重就可以了。

时间复杂度 $O(n\sqrt n \log n)$，块长设了 350。

### [P7447 [Ynoi2007] rgxsxrs](https://www.luogu.com.cn/problem/P7447)

写了[题解](https://www.luogu.com.cn/article/xjilxd9b)。

### [P5355 [Ynoi Easy Round 2017] 由乃的玉米田](https://www.luogu.com.cn/problem/P5355)

P3674加强版，多了一个除法。

只讲除法。

如果 $x>\sqrt N$，直接枚举因子。

如果 $x\le\sqrt N$，不放进莫队，单独处理。

对于每个 $x$ ，记 $las_i$ 表示数字 $i$ 上次出现的位置，$res_i$ 表示位置 $i$ 出现能够除出来答案的最小的 $l$

$las_i$ 直接在每个位置维护，然后用 $las_{a_i\times p},las_{\frac {a_i}p}$ 来更新 $res_i$。

两部分都是 $O(n\sqrt n)$ 的。

### [P4688 [Ynoi Easy Round 2016] 掉进兔子洞](https://www.luogu.com.cn/problem/P4688)

`bitset` 神奇用法。

考虑如何维护一个区间中有多个数，想到用桶，但是过不了。

想到 `bitset`，但是没法维护同一个值出现多次。

由于每次只加入一个数，那么想一种更为巧妙的方法：

$pos_i$ 表示比 $i$ 小的数的个数 +1。

每次修改 $pos_i+cnt_i$ 即可。

然后询问需要分成三个部分。

### [P12013 [Ynoi April Fool's Round 2025] 牢夸](https://www.luogu.com.cn/problem/P12013)

智力堪忧。

观察没有选择的区间长度至少为 2 时，答案一定是一个数，因为如果答案是超过两个数，一定不如把它换成这个区间中最大的那个数。

正解就是答案区间长度至多为 3，因为如果长度为 4 一定能拆成两个 2，那么一定不如选其中更大的那个。

### [P9058 [Ynoi2004] rpmtdq](https://www.luogu.com.cn/problem/P9058)

不是吧，怎么有人机交了两页结果原因是把 $rt$ 写成 $x$。

考虑点分治后求支配点对。

支配的条件显然是 $x<y<z$ 且 $dis(x,z)>dis(y,z)$，那么 $(x,z)$ 就是没用的。

由于是取 $\min$ ,所以对于每个点分中心我们可以视 $dis(x,y)=dis(x,rt)+dis(rt,y)$,因为总有一个点分中心是对的。

那么也就是说如果对于 $x<y<z$ 且 $d_x,d_y<d_z$ ，那么 $(x,z)$ 显然没用了（被 $(x,y)$ 支配了）。

$x>y>z$ 的情况是对称的。

所以在每个点分中心我们找到满足 $d_y<d_x$ 的最大 $y<x$ 和最小 $y>x$，这个按照 $x$ 排序后单调栈维护（这样常数小）。

这样支配对是 $O(n\log n)$ 级别的，后面就是简单的二位数点，复杂度 $O(n\log ^2n+q\log n)$。

正在渲染内容...