摘要：
考虑设计一个哈希函数 \(hash(x) = f(x) \times base^x\)。 其中 \(f(x)\) 表示 \(\sum_{j=1}^{i-1} [j <i]\)。 然后类似于滑动窗口计算区间哈希值，加入一个数就计算贡献，减去一个数就计算这个数产生了贡献，两个东西都可以树状数组维护，那么 阅读全文
posted @ 2024-01-30 23:58
ChiFAN鸭
阅读(22)
评论(0)
推荐(0)
摘要：
相信很多人在学习莫队，刷莫队题目时，会不可避免的遇到一个数据结构 —— 值域分块。这篇文章就是帮助各位快速入门的。 Q1 给定一个序列，实现单点修改以及区间查询，保证修改次数不超过 \(10^7\) 次，查询次数不超过 \(10^5\) 次，序列长度不超过 \(10^5\) 。 A1 首先要求的是 阅读全文
posted @ 2024-01-30 23:58
ChiFAN鸭
阅读(517)
评论(0)
推荐(1)
摘要：
因为是图上路径是否经过某个点的问题，所以考虑建出圆方树，然后根据圆方树的性质，\(a\) 到 \(c\) 存在经过 \(b\) 的路径等价于 \(a,c\) 在圆方树上的路径经过 \(b\) 或者 \(b\) 所连接的方点，考虑暴力在圆方树上跳 LCA 即可，时间复杂度 \(O(n + m)\)。 阅读全文
posted @ 2024-01-30 23:57
ChiFAN鸭
阅读(42)
评论(0)
推荐(0)
摘要：
考虑二分答案。 假设当前二分的答案为 \(k\)，那么对于每个点，距离大于等于 \(k\) 的点构成了平面上 \(4\) 个子平面。 那么只需查询子平面中是否存在点即可，类似于窗口的星星，把问题转换成求矩形交集，用一个扫描线维护，复杂度 \(O(n \log V)\)，加上二分，总复杂度 \(O(n 阅读全文
posted @ 2024-01-30 23:57
ChiFAN鸭
阅读(35)
评论(0)
推荐(0)
摘要：
不知道为什么最近突然变得很摆，又要上文化课，只有一些空余时间可以搞 OI，所以就制定一个写题计划吧。 可能会添加，但是 不会 删除，请各位监督。 Yuno loves sqrt technology I（代码复杂度正确，常数较大还未卡过） 时代的眼泪（已 AC） Happy Sugar Life P 阅读全文
posted @ 2024-01-30 23:57
ChiFAN鸭
阅读(11)
评论(0)
推荐(0)
摘要：
前言 斜率优化是一种经典的单调队列优化类型，虽然它的名字很高大上，但是其思想内核非常简单，这篇博客就是用来帮助各位快速入门的 提示：本博客以单调队列的思想理解斜率优化 引入 dp 优化可以怎么分类？ 数据结构维护决策点集的插入与查找 算法维护决策点集大小，取出无用决策点 而斜率优化 dp 属于第二者 阅读全文
posted @ 2024-01-30 23:57
ChiFAN鸭
阅读(43)
评论(0)
推荐(0)
摘要：
前言 模拟赛离正解就差一个这个，气 正文 线段树上的边分两类：向上连的边，可以优化连出的边，向下连的边，可以优化连入的边。这是线段树优化的基础 构造出线段树，线段树上每一个点代表一个 虚拟 节点，同时父亲连向它的两个儿子 假若点 \(x\) 向区间 \([l,r]\) 内所有点连边，我们这么做： 假 阅读全文
posted @ 2024-01-30 23:57
ChiFAN鸭
阅读(17)
评论(0)
推荐(0)
摘要：
CF19E 问题显然可以转换成找到所有奇环交。 然后建出 dfs 树。 然后考虑利用返祖边得到所有环。 但是注意这里不可以删去偶环上的边。 然后再边上边差分打 \(tag\)。 或者考虑线段树分治套可撤销并查集秒杀。 AT_keyence2019_e 考虑分治，分治完连边构造 MST。 CF76A 阅读全文
posted @ 2024-01-30 23:57
ChiFAN鸭
阅读(26)
评论(0)
推荐(0)
摘要：
来一发 \(O(\log n)\) 线性空间的解法。 考虑通过只维护线段树叶子节点的虚树的方法压缩空间，考虑记录下每个节点的编号，然后通过异或完求最低位的 \(1\) 的方式求出 LCA 的深度，然后记录下 LCA 右端点的编号。在回收节点的时候可以释放储存右端点编号的空间，但是这里为了方便就不这样 阅读全文
posted @ 2024-01-30 23:57
ChiFAN鸭
阅读(17)
评论(0)
推荐(0)
摘要：
看到现有的一篇 DSU on tree 的题解复杂度假了，于是我来再写一篇。 首先重新梳理思路，维护每棵子树内深度为某个值的节点是否存在。 维护这个东西可以直接 DSU on tree 也就是把小的子树内的信息加入大的子树。 然后加入点是判断是否能和已经存在的点构成长度为 \(K\) 的路径。 举个 阅读全文
posted @ 2024-01-30 23:57
ChiFAN鸭
阅读(25)
评论(0)
推荐(0)
摘要：
设计 \(f_i\) 表示以第 \(i\) 个数结尾的选择的最大值。 有 \(f_i = f_j + a_i\)（\(type_i \not = type_j\)）。 发现可以选择的种类其实构成两段连续区间。 所以维护使得 \(type_x = i\) 的所有 \(x\) 的 \(f_x\) 最大值 阅读全文
posted @ 2024-01-30 23:57
ChiFAN鸭
阅读(22)
评论(0)
推荐(0)
摘要：
先不管值域，设计状态 \(dp_{i,j}\) 表示考虑前 \(i\) 个数最后一个数为 \(j\) 的方案数，那么有如下转移： \[dp_{i,j} = dp_{i-1,k} (j \not = k,j \leq a_i) \]先滚动数组去掉一维状态，然后发现每一次操作对于数组 \(dp\) 而言 阅读全文
posted @ 2024-01-30 23:57
ChiFAN鸭
阅读(13)
评论(0)
推荐(0)
摘要：
来一发 \(O(n \sqrt n)\) 时间，\(O(n)\) 空间的分块写法。 首先建模，把 数值 \(x\) 在两个数组中出现的位置作为坐标，问题就转化为一个二维动态数点。 考虑用序列分块维护第一维，第二维用 值域分块 维护，这样子平衡复杂度玩就得到一个 \(O(n \sqrt n)\) 时间 阅读全文
posted @ 2024-01-30 23:57
ChiFAN鸭
阅读(24)
评论(0)
推荐(0)
摘要：
这个东西貌似就是把奇奇怪怪的多模匹配问题变成树论或者图论问题，然后跑 tarjan 或者奇奇怪怪的 DS。 当然，有时候你需要拆贡献或者用一些 string 独有的性质。 就先写到这里吧，我要睡觉了。 阅读全文
posted @ 2024-01-30 23:57
ChiFAN鸭
阅读(11)
评论(0)
推荐(0)
摘要：
前言 我们都知道动态开点权值线段树的空间复杂度是 \(O(n \log V)\) 的，但是很多题目中这样的空间是会被卡的，那我们能不能优化呢？ 实现 看看下面这一棵树： 在上图中，红色节点使我们平常会开的点。 但是我们发现，其实只要维护绿色的点和红色的叶子结点。 其实，绿色节点就是所有叶子结点的 虚 阅读全文
posted @ 2024-01-30 23:57
ChiFAN鸭
阅读(223)
评论(0)
推荐(0)
摘要：
写点基础的东西。随便写的，勿喷。 top cluster 一个 cluster 是一个联通子图，且至多有两个点与其他部分连接 这两个点被称为 boundary node 其余点被称为 internal node，两个 boundary node 间的路径被称为 cluster path 而我们的树分 阅读全文
posted @ 2024-01-30 23:57
ChiFAN鸭
阅读(434)
评论(0)
推荐(0)
摘要：
暴力容斥复活之路！ \(k=1\) 这个你肯定会。 \(k=2\) 大的放上去，小的放下来。简单贪心。 \(k=3\) 考虑二分答案。 然后考虑判断是否合法。 令当前答案为 \(val\)。 首先钦定最小值在第一行。 然后枚举最大值在哪一行。 现在我们就确定了两行可以填的数的范围。 剩下一行的选择就 阅读全文
posted @ 2024-01-30 23:56
ChiFAN鸭
阅读(45)
评论(0)
推荐(0)
摘要：
A 怎么是重构树板子，放在图上都是水题。 B 考场上只打了一个暴力，赛后发现似乎是很可做的 C 是一个考察状态设计的 dp 以后要多刷 D 是一道数据结构优化 dp 考场上写出来了却因为空间问题挂了 \(15\) 分，菜了 而且被 D 拖了时间，没时间开 B,C 。。。 阅读全文
posted @ 2024-01-30 23:55
ChiFAN鸭
阅读(17)
评论(0)
推荐(0)
摘要：
ChiFAN 的进程表 tip 有些题写了题解，思路做法都在里面，就只丢一个传送门了。 2023.1.9 生日蛋糕 传送门 IDA* 经过一番推式子可得，若还剩下 \(K\) 的体积，表面积为 \(2 \times K / R\) 。 所以 \(R\) 要尽可能大。 那么估价函数 \(g(u) = 阅读全文
posted @ 2024-01-30 23:52
ChiFAN鸭
阅读(91)
评论(0)
推荐(0)
摘要：
模拟考最后一题是这道题，要是数组开大就场切了，最后不小心挂了 \(15\) 分。 以下是考场思路： 考虑这样一个问题，所有时间对 \(r+g\) 取余是可以的。毕竟红绿灯是一个循环。 再考虑这样一个东西，等过一次红灯后的所有情况是相似的，从循环的角度出发都是时刻 \(0\)。 因此考虑处理出出发之后 阅读全文
posted @ 2024-01-30 23:52
ChiFAN鸭
阅读(37)
评论(0)
推荐(0)
摘要：
前言 本博文讲述值域分块的进阶用法。由于博主很菜，所以遇到错误欢迎各位在评论区指出。 值域分块入门 模意义查询 Q1 每次给定二元组 \((x,y)\)、模数 \(m\)，以及一个区间 \([l,r]\)。求出有多少 \(i\in [l,r]\) 满足 \((a_i+x)\bmod m<(a_i+y 阅读全文
posted @ 2024-01-30 23:52
ChiFAN鸭
阅读(114)
评论(0)
推荐(0)
摘要：
Day1 Gym101365F 传送门 按照题意用平衡树维护即可，操作本质上是平衡树上二分和删除前 \(k\) 大。 #include<bits/stdc++.h> #pragma GCC optimize(2) #define int long long using namespace std; 阅读全文
posted @ 2024-01-30 23:52
ChiFAN鸭
阅读(38)
评论(0)
推荐(0)
摘要：
显然，我们维护的答案具有 可差分 性，所以转换为 \([1,r]\) 上的查询。 首先，对于 \(x,y,a_i\) 先对 \(m\) 取模不影响结果。 下面为了方便令 \(v = a_i\)。 如果 \(x>y\)。 则一定是 \(x+v-m<y+v\)。 有 \(m \leq x+v\) 且 \ 阅读全文
posted @ 2024-01-30 23:52
ChiFAN鸭
阅读(24)
评论(0)
推荐(0)
摘要：
直接计数其实不好记，不如计数转期望。 令 \(f_i\) 表示点 \(i\) 成为制高点概率，不难发现期望就是 \(\sum f_i\)。 根据定义对于 \(f\) 我们有如下转移 \(f_i = \frac{\sum_{j=l_i}^{r_i} f_j}{r_i-l_i+1}\) 又因为 \(l_ 阅读全文
posted @ 2024-01-30 23:52
ChiFAN鸭
阅读(165)
评论(0)
推荐(0)
摘要：
有一个很暴力的解法，就是以询问点为根 DFS。 考虑优化，我们考虑优化换根。 当根节点从父亲移动到它的某个孩子时，孩子的子树内所有点深度减 \(1\) 其余点深度加 \(1\)。 同理，当根节点从某个节点移动到它的父亲时，它的子树内所有点深度加 \(1\) 其余点深度减 \(1\)。 那么考虑把询问 阅读全文
posted @ 2024-01-30 23:52
ChiFAN鸭
阅读(38)
评论(0)
推荐(0)
摘要：
显然是一个博弈论题，考虑 dp。 定义状态 \(dp_i\) 表示先手走到 \(i\) 之后是否有必胜策略，不难发现以下几点： 若走到 \(i\) 之后无路可走，那么就必败。 若走到 \(i\) 之后对手只能走到一个必败点那么这就是必胜点。 除开以上两种情况都是必败点。 用 \(1\) 表示必胜，\ 阅读全文
posted @ 2024-01-30 23:52
ChiFAN鸭
阅读(20)
评论(0)
推荐(0)
摘要：
很失败啊 A 题大力分讨，罚了 \(2\) 次 B 题大力分讨，罚了 \(1\) 次 C 题大力 dp 一发过 然后就睡觉了 感觉 CF 打少了智商掉了，被前几题拖了太久 阅读全文
posted @ 2024-01-30 23:52
ChiFAN鸭
阅读(8)
评论(0)
推荐(0)
摘要：
考虑状压。 设计状态 \(dp_{i,j}\) 表示考虑 \(i\) 个数，每个数的使用情况的二进制压缩表示为 \(j\) 的情况下的方案数。 然后去正常转移。 唯一特殊的是将限制放在点上，假若这个点转移时不满足限制直接让其的方案数为 \(0\)。 #include<bits/stdc++.h> # 阅读全文
posted @ 2024-01-30 23:52
ChiFAN鸭
阅读(22)
评论(0)
推荐(0)
摘要：
前言 感谢 P9216 让我见识到巨佬们各种神秘哈希。 以下哈希均为判断数组 \(a\) 是否等于数组 \(b\) 的形式。 并且以下运算都在模意义下进行。 随机权值哈希 好吧这是我写的博客用的 定义随机权值数组 \(v\)，并定义判断 \(\sum_{i} v_i^{a_i}\) 是否等于 \(\ 阅读全文
posted @ 2024-01-30 23:51
ChiFAN鸭
阅读(36)
评论(0)
推荐(0)
摘要：
定义 按照某种确定的关系 \(f\) 可以将 \(A\) 中的任意一个元素映射到 \(B\) 中唯一确定的元素 \(f(x)\) 与之确定。 阅读全文
posted @ 2024-01-30 23:51
ChiFAN鸭
阅读(29)
评论(0)
推荐(0)
摘要：
写出签到（实在不行也可以放弃） 暴力打满（有时候也可以写随机化） 记得对拍（没对拍就紫菜） 干完以上所有事写有把握的题目（DS?） 干完上一件事可以适当颓 阅读全文
posted @ 2024-01-30 23:51
ChiFAN鸭
阅读(22)
评论(0)
推荐(0)
摘要：
放一个比赛链接 先考虑打完暴力后 \(k = 1\) 的特殊性质。 当队列容量为 \(1\) 时，队中的人 \(i\) 会被第一个满足 \(i \leq j\) 且 \(b_i \leq a_j\) 的人淘汰，并且队列中的人会变成 \(j\)，考虑倍增加速这个过程，令 \(f_{i,j}\) 表示第 阅读全文
posted @ 2024-01-30 23:51
ChiFAN鸭
阅读(42)
评论(0)
推荐(0)
摘要：
不难发现，最开始有 \(n\) 条链，并且由于每个点最多有一个桥，所以我们的交换操作实际上等价于将相邻的两条链断开，然后将它们后半部分交换。并且每个点在路径中的相对位置不变。 于是考虑维护这些链。 有一个很直观的思路就是维护点对 \((i,j)\) 表示最开始第 \(i\) 条链的第 \(j\) 个 阅读全文
posted @ 2024-01-30 23:51
ChiFAN鸭
阅读(15)
评论(0)
推荐(0)
摘要：
SAM 定理 SAM 由 parent 树与一张 DAG 构成，他们共用点集。 \(endpos(s)\) 表示 \(s\) 出现的所有位置上最后一个字符所处位置的集合。 SAM 中 DAG 上每条路径对应原串上的一个子串，一个子串也与其对应。 在 SAM 的 DAG 上到达一个点的所有子串的 en 阅读全文
posted @ 2024-01-30 23:18
ChiFAN鸭
阅读(116)
评论(0)
推荐(0)
浙公网安备 33010602011771号