rldcot p7880 2006 ynoi

题意 给定 \(n\) 个数，有 \(m\) 个询问，每个询问给定 \(l\) 和 \(r\)，求出区间 \(l\) 到 \(r\) 中的最小众数出现次数，强制在线。 数据范围：\(n\le 500000\)，空间限制：\(62.5MB\)。 思路 这道题的弱化版是 蒲公英，这道题加强的地方在于数据 ......

好题，牛牛的一个套路。 先树剖一下，我们可以很简单的用树状数组维护每个点的真实值。 对于每个点只维护所有轻儿子的信息，对于每次询问的时候暴力加入当前点，重儿子以及父亲的信息，查询第 \(k\) 大，再删除信息即可。 考虑链修改的影响。因为只维护的是轻儿子的信息，那么只有链上的所有轻边会修改。 具体的 ......

\(\text{Links}\) LuoguBlog P4119 [Ynoi2018] 未来日记 题外话 个人生涯中第一道独立通过的 Ynoi 大分块！！ 同时也是个人生涯中通过的第十道 Ynoi 系列题目！！ 卡了好久结果加了个优化就过了/yun AC 那一瞬间的场面好像 56 Seconds L ......

题意 给定序列 \(s\)，每次询问 \(l, r\) 的区间众数的出现次数。 强制在线。空间：\(62.5MB\)。 Sol 蒲公英卡常卡空间版。 考虑优化那个 \(n \times m\) 的数组。 我们要求 \(l, r\) 之中某个数的个数。 乍一看不好弄，仔细想想就会发现，如果我们知道当前 ......

题意 给定长度为 \(n\) 的序列 \(s\)。 有 \(m\) 个询问，每次询问三个区间，把三个区间中同时出现的数一个一个删掉，问最后三个区间剩下的数的个数和，询问独立。 Sol 不难发现答案即为求：\(r1 - l1 + r2 - l2 + r3 - l3 + 3 - siz\)。其中 \(s ......

题意 给定一个序列 \(s\)，每次修改操作 \(x, y, z\)。 \(i \in [y, y + x, y + 2x, y + 3x, \ldots, y + kx]\)，\(s_i = s_i + z\)。 区间查询 \(\sum_{i = l} ^ r s_i\)。 Sol 根号分治，很明 ......

我永远喜欢数据结构。 题目传送门 给出 \(n\) 个点的树，点有颜色 \(a_i\)。有 \(q\) 次询问，每次询问给出 \(l,r,x\)，求保留 \([l,r]\) 范围内的节点时，\(x\) 所在联通块中有多少种本质不同的颜色。询问之间相互独立。 不保留一个点的定义是，将这个点以及与其相邻 ......

支配点对实在是太有意思了。 本质上就是一个合法的减枝。 思路 考虑维护树上路径问题。 容易想到点分治。 考虑在当前的分治中心 \(\text{rt}\)，每个点到当前分治中心的距离为 \(dp_x\)。 求出每一组点对的贡献。 假设每个点对在距离长的那部分贡献，即 \(dp_i>dp_j\)，求出所 ......

一道很好的启发式合并题目。 思路 考虑一个事实。 我们想要求出对于每个点对不合法的情况。 例如现在考虑到了 \((x,y)\)，它们的 \(\text{lca}\) 为 \(z\)。 有几种情况： \(a_x< a_z< a_y\)，那么是合法的。 \(a_x< a_y< a_z\)，那么包含 \( ......

这题难点在理解题意。没有任何技术含量：( 题目分析：1.“可持续发展”到底什么意思？Make ends meet.也就是说能养活的那些人一年消耗的等于地球一年产生的。 2.题中为什么要给x,a,y,b？为了求等量关系。注意，这里"x 亿人生活 a 年，或供 y 亿人生活 b 年"用的是地球新生的资源 ......

P7907 [Ynoi2005] rmscne 题解 退役前的最后一篇题解，献给 Ynoi。再见了各位。 题目大意 给定一个长度为 \(n\) 的序列和 \(m\) 次查询，对于每次查询，给定 \(l, r\)，求出一个最短的子区间 \([l', r']\)，满足所有在区间 \([l, r]\) 中 ......

lxl 上课讲的题，来写个题解。 样例很强，赞美 lxl！青蛙，呱 ????。 \(\text{rldcot} = \text{range lca depth count on tree}\)。/yiw（猜的）。 题目传送门 给出一棵 \(n\) 个点的有根树。定义 \(\text{LCA}(x,y ......

[Luogu P4548 CTSC2006] 歌唱王国 提前约定：\(\text{border}\) 指的是公共前后缀。 题意 一个无限长的字符串 \(S\)，其中每个字符都是 \([1,n]\) 中的一个随机整数，求对于给定的字符串 \(t\)，\(S\) 中包含 \(t\) 的最短前缀的期望长度 ......

分块，卡常，分块，卡常，分块，卡常，分块，卡常，分块，卡常，分块，卡常，分块，卡常，分块，卡常，分块，卡常，分块，卡常，分块，卡常，分块，卡常，分块，卡常，分块，卡常，分块，卡常，分块，卡常 ......

题意 给定一个序列，静态区间查询区间的长度为 \(1 \to 10\) 的极长值域连续段个数。 Sol 考虑离线下来跑扫描线。枚举右端点，维护每个左端点的答案。 不难想到，\(i\) 对 \(lst[i]\) 是没有贡献的，考虑右端点为 \(i - 1\)，若此时的 \(l \le lst[i]\) ......

首先容易发现将原树自底而上建立 \(\texttt{kruskal}\) 重构树后，相当于要对原树进行单点修改，动态维护重链剖分一个点所在的重链底。由于单点修改不是单点加，和 \(\texttt{ZJOI 2018}\) 历史不同，所以切换次数不是 \(O(n \log n)\) 的，所以可以考虑不 ......

看到不好维护的取模相关信息，想到根号分治。设值域为 \(V\)，根号分治的阈值为 \(B\)。 对于模数不超过 \(B\) 的情况，我们需要利用情况数为 \(O(B)\) 这一性质。在每次插入元素时动态维护所有情况的答案，查询时查表回答即可。 对于模数超过 \(B\) 的情况，我们需要利用商数个数为 ......

P7880 [Ynoi2006] rldcot 题意 区间虚树数颜色。 题解 十分好的一道题目，绕来绕去又绕回最初的思路了。 首先考虑怎么写出 \(O(nq)\) 的暴力，显然就是扫描树上的每一个点，然后判断有没有点跨子树。 然后考虑到我们求的是虚树颜色数，所以考虑莫队，删除和插入都可以通过找前驱和 ......

64MB,1.5s 题目描述 您正在欣赏 galgame 的 HS，然后游戏崩溃了，于是您只能做数据结构题了： 维护一个长为 \(n\) 的序列 \(a_i\)，有 \(m\) 次操作。 将区间 \([l,r]\) 的值修改为 \(x\)。 询问区间 \([l,r]\) 出现了多少种不同的数，也就是 ......

题目传送门 本来不想写这道 \(shabi\) 卡肠题的，但还是写了。 分块+根号分治。 考虑对 \(x\) 的大小分类讨论： 若 \(x>=\sqrt{n}\)，很明显最多只会加 \(\sqrt{n}\) 次，暴力加即可，用分块维护每个块内的 \(sum\)，查询就直接散块加上整块即可。 若 \( ......

给你一个整数数组 nums 和一个整数 k ，请你返回数对 (i, j) 的数目，满足 i < j 且 |nums[i] - nums[j]| == k 。 |x| 的值定义为： 如果 x >= 0 ，那么值为 x 。如果 x < 0 ，那么值为 -x 。 示例 1： 输入：nums = [1,2, ......

题目传送门 先考虑没有区间限制怎么做，即执行完所有操作在询问全局和。用 \(set\) 维护连续段,就是珂朵莉树，写个模板即可。 加上区间限制呢？先将询问按照 \(r\) 排序。又因为还要维护每个 \(l\)，就在颜色段上在记录加入时间。我们在时间维开个数据结构，简单的树状数组即可。时间复杂度 \( ......

题目传送门 看到异或最大值，根据套路不妨考虑 \(0-1 trie\)。 通过 \(trie\) 找到异或值最大的点对 \((x,y)\)。那么除了 \((x,y)\) 到 \(1\) 路径上的点之外，其他的点的答案就是 \((x,y)\) 的异或值。 接下来考虑怎么算出这 \((x,y)\) 到 ......

P7710 [Ynoi2077] stdmxeypz 题解 我的第一道 Ynoi 题，体验感不高，调了大半天，最后发现有个地方 \(B_1\) 写成 \(B_2\) 了。 分析 树上问题，明显是要转到树下的，所以 DFS 序是一定要求的。 有关树上距离，所以 \(deep\) 数组也是一定要求的。 ......

Day \(\text{XXX}\)。 注意到修改是易于复合的立方操作，而且值域非常小，所以可以直接 \(O(v\log m)\) 预处理出对每个 \(i\in[0,v)\) 操作了 \(2^{j}\le m\) 次的结果，维护出每一位被修改了多少次，查询某一位的值直接倍增 \(O(\log m)\ ......

P5313 看到值域比较，又支持离线，可以想到莫队和桶。 考虑先将桶按 \(b\) 分段，将每段分别进行按位与运算，做完第 \(i\) 段时用于运算的桶全都为 \(0\)，就可以直接得到答案。这显然可以用 bitset 优化。但是 STL 的 bitset 不支持分裂操作，所以需要手写。 当 \(b ......

一天一道慢慢写着。因为菜所以一开始只有 easy round。 TEST_68 简化一下限制。注意到很多点都能取到最大值，具体的，若最大值为 \(x,y\) 处取到，那么只有 \(1\rightsquigarrow x,1\rightsquigarrow y\) 路径上的点取不到。而一条链是非常好做 ......

Description 给你一个长为 \(n\) 的排列，\(m\) 次询问，每次查询一个区间的逆序对数，强制在线。 link \(1\leq n,m\leq 10^5\)。 Solution 考虑分块。 首先如果 \(l,r\) 在同一个块内，可以对于每个块暴力二维前缀和预处理。 如果 \(l,r ......

题外话 纪念一下第一道 Ynoi Easy Round.（上次那个是 Ynoi 模拟赛，什么时候才能做正统 Ynoi 啊/ll 在图老师的逼迫下换了洛谷博客的主题和背景，还挺好看的感觉。 原题传送门 题意 给定一个长度为 \(m\) 的序列，初始全为 \(0\)。再给 \(n\) 个区间赋值操作。 ......

P1060 [NOIP2006 普及组] 开心的金明 简单的01背包问题 点击查看代码 #include<bits/stdc++.h> using namespace std; int f[30005]; int main() { int n, m; cin >> n >> m; for (int ......