Ynoi

### [题目传送门](https://www.luogu.com.cn/problem/P5524) ## solution 简单题。 我们正着做扫描线。 设 $t_i$ 表示位置 $i$ 最后一次进行二操作的时间，那么一操作就是交换 $t_x,t_y$ ，二操作就是区间复制。 对于三操作，开一个 ......

## 题目描述 由于你不会设计哥德尔机，所以你决定先做一道数据结构题： 给定一个长度为 $n$ 的序列 $a_1\cdots a_n$。你需要回答 $m$ 个询问，第 $i$ 个询问给定一个区间 $[l_i,r_i]$，请你求出这个区间中所有非空子集的最大公约数的乘积。由于答案可能很大，每次询问请你 ......

### [题目传送门](https://www.luogu.com.cn/problem/P8512) ## solution 简单题，考虑正着做扫描线，维护最后一次覆盖每个位置的修改时间，这个可以用 $set$ 维护颜色段数均摊。 那么显然对于一个以当前位置为右端点的询问，其答案就是所有最后修改时 ......

[更好的阅读体验。](https://www.cnblogs.com/Ender32k/p/17125914.html) 假设值域为 $v$ 即 $10^5$，显然每个质因数 $p$ 独立，考虑计算每个 $p$ 对答案的贡献。 $p$ 对答案的贡献次数为 $\sum\limits_{S\subset ......

这东西在线不太能做，考虑离线扫描。扫描右端点 $r$，我们对每个位置 $l$ 维护一个 $p_l$ 表示最小的 $p$ 使得 $[l,p]$ 是 $[l,r]$ 的合法子区间。 考虑如何维护 $p_l$。考虑新加入的右端点 $r$，加入一个数 $a_r$，上一次出现的位置为 $lst_{a_r}=c ......

| | $\quad\mathcal{Problem\ \ ID}\quad$ | $\quad\quad\mathcal{Name}\quad\quad$ | $\quad\quad\mathcal{Time}\quad\quad$ | | : : | : : | : : | : : | | $\ ......

# Luogu P6109 [Ynoi2009] rprmq1 [Luogu P6109](https://www.luogu.com.cn/problem/P6109) ## 题目背景 我谔谔 本题读入量约 13 MB，输出量约 7 MB，请选择合适的输入输出方法 ## 题目描述 有一个 $n \ ......

首先将修改操作差分为 $l_1$ 时刻给 $[l_2,r_2]$ 中的值 $+v$，$r_1+1$ 时刻给 $[l_2,r_2]$ 中的值 $-v$。这样第 $i$ 行的状态相当于执行 $1\sim i$ 时刻的操作后的状态。 猫树分治，把一个询问挂在线段树上满足 $l\le l_1\le mid\ ......

[Problem Link](https://www.luogu.com.cn/problem/P9062) 给定平面上 $n$ 个点，$Q$ 次询问编号在 $[l,r]$ 内的点的最近点对。$n,Q\le 2.5\times 10^5$。 技巧：平面网格化 乱搞都是错的。看见欧几里德距离，想到平面 ......

大家可以猜猜看为什么有两个标题，因为这个原因本文就不设密码了。 5 月模拟赛，6 月补题，7 月补 sol，不愧是我。 ## 题目描述 [link](https://www.luogu.com.cn/problem/P5065)。 赛时得分：0/0。 完全不会，暴力都没打。 首先，有个经典结论：前缀 ......

[洛谷传送门](https://www.luogu.com.cn/problem/P7722 "洛谷传送门") 被踩爆了好神的题啊！ 转化一下题意，给出三个数组 $a, b, c$，每次可以单点修改 $a, b, c$，询问即求 $b_i = a_j = c_k, 1 \l ......

Ynoi 4血！我永远喜欢珂朵莉！ 原题链接 珂朵莉给了你一个序列，每次查询一个区间 [l,r][l,r] 中所有子序列分别去重后的和\pmod p(modp)。 首先这是一个静态问题，还不强制在线，而且是 Ynoi 的黑题。 于是们就可以想到大概是一个离线算法，并要求解序列问题。 莫队算法 首先我 ......

[题目 Link](https://www.luogu.com.cn/problem/P8264) 我们不妨来考虑所有询问都是 $l=1,r=n$ 的情形，这种情况下需要对每个值处理出他经过一系列变换后变成了什么数。 考虑用 $\text{solve}(p,l,r)$ 表示我们现在要计算 $x\in ......

> 二阶堂真红给了你一个长为 $n$ 的序列 $a$，有 $m$ 次操作 > > 1. 把区间 $[l,r]$ 中大于 $x$ 的数减去 $x$。 > 2. 查询区间 $[l,r]$ 中 $x$ 的出现次数。 > > 对于 $100\%$ 的数据，$1\le n\le 10^6$，$1\le m\l ......

分块。我们先来考虑修改对整块的影响。记值域为 $V=10^5$。 考虑对每一块维护 $V$ 个集合 $S_1,S_2,\cdots,S_V$，第 $i$ 个集合 $S_i$ 维护了区间中所有 $=i$ 的元素的一些信息，并维护区间的最大值 $m$，对于一次操作 $x$： - 若 $m\le 2x$， ......

[题目 Link](https://www.luogu.com.cn/problem/P5046) 分块，首先预处理所有整块之间的答案，这部分用类似莫队二离的手法可以改成 $O(n)$ 次插入和 $O(n\sqrt{n})$ 查询，然后根号平衡一手做到 $O(n\sqrt{n})$；空间自然也是能线 ......

对于这类问题，我们有一种比较通用的解法是设定一个贡献的充要条件。我们通常会在若干个都能产生某一贡献 $p$ 的元素 $a_1\dots a_k$ 上定义一种小于关系 $R$，每次只让这些元素中的极小值进行贡献。具体来讲我们可以对每个元素求出它上/下一个比它“小”的元素 $pre_x,suf_x$，那 ......

我们先不考虑 $dep$ 的问题，先来研究有多少种不同的 $lca(i,j)$。 考虑改询问为贡献，计算一个 $l$ 可以成为哪些 $(i,j)$ 的 lca。这个东西可以写成若干个点对对吧，倘若我们忽略掉一共有 $O(n^2)$ 个点对的事实的话，我们的问题就转化成了有若干个被染成某些颜色的区间， ......

### 「Ynoi2011」成都七中 题意：询问 $([l,r],x)$，表示将树中编号在 $[l,r]$ 内的所有节点保留，求 $x$ 所在连通块中颜色种类数 可以转化为从 $x$ 出发且只经过节点范围在 $[l,r]$ 的路径上的颜色种类数，是路径问题且多次询问，所以可以考虑点分树 但是可以发现 ......

[Ynoi2016] 镜中的昆虫 P4690 [Ynoi2016] 镜中的昆虫 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述 您正在欣赏 galgame 的 HS，然后游戏崩溃了，于是您只能做数据结构题了： 维护一个长为 $n$ 的序列 $a_i$，有 $m$ 次操作。 ......

[Ynoi2018] 天降之物 这个根号分治太神啦。 首先考虑一个朴素的暴力：对每个数维护出现位置的 std::vector 这样查询可以两个指针遍历 std::vector 做到平方复杂度。 注意到复杂度和出现次数有关，那么就可以考虑阈值分治了，然而合并的操作使得我们不好维护信息。 先考虑不带修的 ......

RE了大约12次以后，SoN3ri告诉我是bitset开小了。 那你为什么全RE了啊（？ 题意是给你一个长度为 $n$ 的序列，一共 $m$ 次询问，每次询问包含三个区间，求三个区间内相同的数去掉后剩下的数的个数。 做完了小清新人渣的本愿，看啥都是bitset+莫队，这题我也是一开始打了一个莫队+b ......

~~md调了5h才调出来恶心坏了没想到这么快就做了第二道Ynoi~~ ~~据说这题其实不卡常~~ 屠龙宝刀点击就送 题面也很清楚，给定两种操作，一种是区间加，一种是询问区间内第 k 小的数的值是多少。 对于区间加，在分块入门系列里面是直接对于修改过的散块进行重排，剩下的直接用 tag 来标记，我也是 ......

~~第一道 Ynoi 也可能是最后一道了~~ 题面的意思挺简洁，对于每一次询问的 $l,r$ 求所有的子区间内的元素和，其中子区间内的元素要去重再进行求和。 首先我们可以想到，对于一个长度为 $n$ 序列的子区间个数是 $2^{n}$，如果要是里面全都是一个数 $a^{i}$ 的话，那么对于 $1, ......

[Ynoi2013] 无力回天 NOI2017 首先看到异或，想到能维护异或的东西就那几样（线性基/01trie/数位 dp/FWT），再看到求选任意个数后的异或最大值，线性基无疑了。 这时再看还要维护什么其它信息，区间异或，区间查询，一副线段树维护线性基的样子。但我们知道线性基中的值一旦修改就必须 ......