- 2024-08-08记 Ynoi
决定写写Ynoi。P4119[Ynoi2018]未来日记最初分块。也是第一次品尝的Ynoi大分块。1lrxy将\([l,r]\)区间内的\(x\)全部变成\(y\)。2lrk查询\([l,r]\)区间内的第\(k\)小值。查询第\(k\)小看起来是个非常复杂的操作,一般来说看到这个想到的是二分
- 2024-05-24Ynoi 做题记录
[Ynoi2011]初始化第一道通过的Ynoi题,虽然似乎大概也许并不太难。题目分析查询操作为求区间和,可以使用分块。看到这种修改操作满足“跳着加”性质的题目,可以尝试根号分治。那么如何进行根号分治呢?当\(x\ge\sqrt{n}\)时,需要修改的位置最多有\(\sqrt{n}\)个,故可以暴力
- 2024-03-12Ynoi 大分块选做
第二分块linkCF版本题意:给出一个序列\(a_{1...n}\),有\(m\)次操作。每次:修改:给出\(l,r,x\),表示把区间\([l,r]\)中\(>x\)的数减去\(x\)查询:给出\(l,r,x\),求\([l,r]\)中有多少个数\(=x\)\(1\len\le10^6,\space1\lem\le5\times10^5,\space0\lea_i,x
- 2024-03-07P9989 [Ynoi Easy Round 2023] TEST_69 题解
分析考虑线段树。\(20\)分统计节点懒标记,在每次询问之前统一下传\((lst,i-1)\)的修改懒标记,\(lst\)是上一次询问的位置。\(40\)分在统一下传的过程中打标记,如果当前节点的某个儿子所在子树中没有需要下传懒标记的节点,则不更新那个儿子的内容。\(70\)分注意到\(a\)
- 2024-02-28Ynoi 大分块系列
最初分块先考虑怎么用分块维护区间第\(k\)小。首先肯定想到二分区间第\(k\)小,然后查询区间有多少个数小于等于\(x\)。但这样时间复杂度是\(\operatorname{O}(n\sqrt{n}\log^2n)\)的,无法通过此题。考虑这样一个事情,我们可以暴力枚举区间第\(k\)小,然后查询区间内有多
- 2024-01-30WC2024 Lectures
大概只会有例题题解。目录P8263「YnoiEasyRound2020」TEST_8P8263「YnoiEasyRound2020」TEST_8Tag:S-持久化WBLT。使用WBLT来维护整个括号序列,则三四操作已经做完了。考虑一二操作,使用倍增的方式处理出复制\([l,r]\)区间的结果,于是可以在\(O(\logk)\)的复杂度内
- 2024-01-19P8512 [Ynoi Easy Round 2021] TEST_152 题解
题目链接:[YnoiEasyRound2021]TEST_152题目比较抽象,翻译一下。就是有\(n\)个操作,每个操作为\((l_i,r_i,v_i)\)表示把长为\(m\)序列\(a\)的\([l_i,r_i]\)上的数覆盖为\(v_i\)。而查询为\([time_l,time_r]\),表示从\(time_l\)的操作开始执行,到\(time_r\)操作结
- 2024-01-13Ynoi
P4688[Ynoi2016]掉进兔子洞序列,静态,求三个区间的可重集的交的大小,离线,\(n,Q\le10^5\),3s,500MB缺乏性质\(\rightarrow\)bitset静态区间\(\rightarrow\)莫队化为单点改bitset支持取交,\(x\)重复\(cnt_x\)次即可,空间\(O(n^2/w)\),时间\(O(n\sqrtn+{n^2\overw})\),分
- 2023-12-29小题狂练 (B)
先放这吧,不一定啥时候能做完呢.目录[YnoiEasyRound2023]TEST_69[WC2020]猜数游戏[YnoiEasyRound2023]TEST_69势能线段树,每个点只有log次有效修改,维护区间lcm即可知道需不需要向下递归修改.可以把lcm与1000000000000000003取min会少一些细节.[WC2020]
- 2023-12-29P9994 [Ynoi Easy Round 2024] TEST_132 题解
题解怎么都是用暴力日过去的啊。思路考虑根号分治,设阈值为\(B\)。对于第二维出现次数超过\(B\)的,我们可以在修改时暴力更改,这部分复杂度为\(O(\frac{nm}{B})\)。对于第二维出现次数小于\(B\)的,我们可以在修改是打标记,查询时遍历一遍,这部分的复杂度为\(O(mb)\)。大多数
- 2023-12-29P9991 [Ynoi Easy Round 2023] TEST_107 题解
思路题目即要求删除区间中的一个或多个颜色。考虑假如枚举删除颜色\(k\)。那么在\(l,r\)中的答案为:\[\max_{i=1}^{m+1}a_i-a_{i-1}\]其中\(a_i\)为颜色\(k\)在\(l\simr\)中的出现位置,\(a_{0}=l,a_{m+1}=r\)。可以分类讨论。答案为\(a_1-l\),那么只需要维护\(
- 2023-12-21[Ynoi2007]rfplca/[CF1491H] Yuezheng Ling and Dynamic Tree
题目描述给定一棵大小为\(n\)的\(1\)为根节点的树,树用如下方式给出:输入\(a_2,a_3,\dots,a_n\),保证\(1\leqa_i<i\),将\(a_i\)与\(i\)连边形成一棵树。接下来有\(m\)次操作,操作有两种:1lrx令\(a_i=\max(a_i-x,1)(l\leqi\leqr)\)。2uv查询在当前的\(a\)
- 2023-11-03「杂题乱写」Ynoi
「杂题乱写」Ynoi点击查看目录目录「杂题乱写」YnoiP7710[Ynoi2077]stdmxeypzP5356[Ynoi2017]由乃打扑克P5309[Ynoi2011]初始化P5046[Ynoi2019模拟赛]YunolovessqrttechnologyI由于Ynoi道道卡常且常数受一些常量影响较大,为方便表示复杂度,本文记阈值为\(B\)
- 2023-10-09P8511 [Ynoi Easy Round 2021] TEST_68
题目传送门看到异或最大值,根据套路不妨考虑\(0-1trie\)。通过\(trie\)找到异或值最大的点对\((x,y)\)。那么除了\((x,y)\)到\(1\)路径上的点之外,其他的点的答案就是\((x,y)\)的异或值。接下来考虑怎么算出这\((x,y)\)到\(1\)路径上的点的答案,可以直接暴力计算!
- 2023-10-06jiaxun ynoi
一天一道慢慢写着。因为菜所以一开始只有easyround。TEST_68简化一下限制。注意到很多点都能取到最大值,具体的,若最大值为\(x,y\)处取到,那么只有\(1\rightsquigarrowx,1\rightsquigarrowy\)路径上的点取不到。而一条链是非常好做的,直接dfs下来就行。时间复杂度\(\math
- 2023-09-14YNOI 做题记
YNOI做题记偶然有一天做到了其中的一道题,于是便开始做相关的题了……[Ynoi2015]我回来了-洛谷这之一场联考搬过来的题……于是考场上写了一个\(O((n+m)\log^2n)\)的代码,然后成功被卡掉,非常慢速。其实离线,将每一个伤害答案变化的时间做出来,然后加入时间序列后,树状数组
- 2023-08-24Ynoi 盼君勿望
1.1前言在太阳西斜的这个世界里,置身天上之森,等这场战争结束之后,等这场战争结束之后,人人本着正义之名,长存不灭的过去,逐渐消逝的未来,我回来了,纵使日薄西山,即使看不到未来,此时此刻的光辉,盼君勿忘,世界上最幸福的女孩珂朵莉要永远幸福的呀~题目链接。1.2题目描述珂朵莉给了你
- 2023-06-21洛谷 P8264 [Ynoi Easy Round 2020] TEST_100
题目Link我们不妨来考虑所有询问都是\(l=1,r=n\)的情形,这种情况下需要对每个值处理出他经过一系列变换后变成了什么数。考虑用\(\text{solve}(p,l,r)\)表示我们现在要计算\(x\in[l,r]\)的这些数在经过\(x\leftarrow|x-a_p|,x\leftarrow|x-a_{p+1}|\),一直到\(x\leftar
- 2023-01-27Solution Set -「DS 专题」兔年的兔子写 DS 会有小常数吗?
目录Day1「Ynoi2009」「洛谷P6109」rprmq1^「YnoiEasyRound2021」「洛谷P8512」TEST_152「Ynoi2005」「洛谷P7907」rmscne「Ynoi2010」「洛谷P6105」y-fasttr
- 2023-01-23CTS 2023 游记【脱敏版】
该版本删去了一些可能敏感的信息.2023.12.16前几天和戴老师聊天的时候想能不能给CTS投点题什么的,如果又全是Ynoi题就不好了呢.毕竟前段时间lxl[数据删除],这是
- 2023-01-01Ynoi
Ynoi大战Ynoi系列,顺序是洛谷题号排序。已经有标题但是还没写sol的是因为博主是个大鸽子。P4690区间赋值,区间数颜色。考虑静态询问区间颜色总数的经典问题怎么做?定
- 2022-12-24Ynoi记录
\(\quad\mathcal{Problem\\ID}\quad\)\(\quad\quad\mathcal{Name}\quad\quad\)\(\quad\quad\mathcal{Time}\quad\quad\)\(\texttt{1}\)\(\textrm{5354}\)\(
- 2022-12-19洛谷 P6580 [Ynoi 2019] 美好的每一天~ 不连续的存在 题解
既然是YNOI那肯定是要分块的。先考虑树是一条链的情况,可以直接回滚莫队,对n个节点组成的序列分块。在回滚莫队的过程中,当前维护的区间一共会扩展\(O(n\sqrtn)\)次,每次都是
- 2022-12-19Ynoi 切(受)题(虐)记录
防止忘记做法大致按照切题顺序简略写一下思路,同时造福一下社会。(不过我怀疑大概只有我能看懂我自己写的。)缓慢更新。P4119[Ynoi2018]未来日记最初分块。人生第一道
- 2022-12-09Ynoi 数据结构题选做
Ynoi数据结构题选做前言我将成为数据结构之神!坚持lxl党的领导,紧随nzhtl1477(女装灰太狼1477)的脚步。无论过去、现在还是未来,分块始终是实现datastructures伟大复