2023省队集训
2023省队集训
模拟赛
Day3
T1
给定 $n$ 点简单无向图, 对每对 $(x, y)$ 求是否有一条 $x$ 开始 $y$ 结束的哈密顿路.
$n\le 24$
注意到因为哈密顿路一定经过所有点, 所以对于 $x\to y$ 可以拆成 $1\to x, 1\to y$.
考虑求出 $f_S$ 表示经过 $S$ 能走到哪些点, 然后枚举每一个 $S$, 对于其中每一个 $x$, 考察 $f_{U/S}$ 是否包括 $y$, 复杂度是 $n2^n$.
至于如何求 $f_S$, 考虑每次对于 $f_S$, 轮流拿出其中的点扩展一个得到新的 $f$, 复杂度是 $n2^n$
总复杂度 $n2^n$
T2
对于 $100%$ 的数据, $1 \leq n, q \leq 10^6$, $1 \leq l_i \leq n$, $1 \leq H, a_i \leq 10^{12}$, $1 \leq t_i \leq 3$.
相当于给了三种函数:
- $f(x)=\begin{cases}x-a_i, x\ge a_i\-inf, x<a_i\end{cases}$
- $g(x)=\begin{cases}a_i, x\ge a_i\-inf, x<a_i\end{cases}$
- $h(x)=\begin{cases}-inf, x<0\ x, x\ge a_i\a_i, x<a_i\end{cases}$
考虑函数复合后的形式:
- 如果内层函数是 $g$, 嵌套后两个分支是对 $a$ 判断后直接赋值
- 如果内层函数是 $f$, 大量 $f$ 相当于减去总的该减的不然变成 $0$.
- 内层函数是 $h$ 也是判断后直接赋值.
重点就是几种情况都只在外面判断后里面保留一个分支, 于是任意层函数嵌套后形式为 $m(x)=\begin{cases}-inf, x<a\ y, x\in [a, b] \ x-b+y, x>b\end{cases}$.
于是直接线段树维护函数复合. 配个二分.
lxl讲课
支配对问题
指的是, 对于询问某些对 $(a, b)$ 的贡献, 可以通过贪心干掉一些无意义对, 保留数量可接受的支配对.
第一类支配对
利用贡献本质只有 $O(n)$ 种使得可以枚举了上面两个中的一个贡献.
用启发式合并搞定对于某个确定的lca的点对数.
P7880 [Ynoi2006] rldcot
给定一棵 $n$ 个节点的树, 树根为 $1$, 每个点有一个编号, 每条边有一个边权.
定义 $dep(x)$ 表示一个点到根简单路径上边权的和, $lca(x, y)$ 表示 $x, y$ 节点在树上的最近公共祖先.
共 $m$ 组询问, 每次询问给出 $l, r$, 求对于所有点编号的二元组 $(i, j)$ 满足 $l \le i, j \le r$ , 有多少种不同的 $dep( lca(i, j))$.
$n\le 10^5$
考虑支配对, 对于一个点作为lca, 需要有 $(a, b)$ 处于其不同子树, 目标是保留尽量少的对.
容易发现, 对于点 $x$, 只需要保留其在其他子树对前驱后继形成的对 $(pre, x), (succ, x)$ 即可. 但如果对其他每个子树分别搞出来数量还是 $n^2$ 的.
考虑每次把一个子树的点合并进当前子树, 正确性显然, 这样只有 $n\log n$ 个点对.
那么下面的问题是处理本质不同, 把问题抽象到平面上, 每个询问对应一个点, 一个点对贡献一个 $2-side$ 矩形, 注意到 $2-side$ 矩形并再拆成不交矩形数是线性的, 于是每次把面积并内的询问都加一就行了.
复杂度 $n\log^2 n+m\log n$
P8528 [Ynoi2003] 铃原露露
给定一棵有根树, 顶点编号为 $1, 2, \dots, n$, 对 $2\le i\le n$ 有 $f_{i}$ 为 $i$ 的父亲. $a_1, \dots, a_n$ 是 $1, \dots, n$ 的排列.
共 $m$ 次询问, 每次询问给出 $l, r$, 询问有多少个二元组 $L, R$, 满足 $l\le L\le R\le r$, 且对任意 $L\le a_x\le a_y\le R$, 有 $x, y$ 在树上的最近公共祖先 $z$ 满足 $L\le a_z\le R$.
以上所有数值为整数.
$1\le n, m\le 2\times 10^5$, $1\le f_i\le i-1$, $l\le r$.
考虑这个相比上一个多套了个区间, 但上一个单点查, 所以这个仍然先求有贡献的内层 $L, R$, 然后矩形查.
那么考虑有贡献的对 $(x, y, z)$, 如果 $a_z\in [a_x, a_y]$ 则是废物, 否则如 $a_z<a_x\le a_y$, 则会消去一个 $[a_z, a_x]\times [a_y, inf]$ 的3side矩形. 接下来只说这样的.
接下来枚举 $z$, 对于同一个 $x$, $y$ 一定是不同子树内的 $a$ 最小的, 于是又可以用启发式合并消到 $n\log n$.
然后求矩形内不被矩形覆盖的面积, 扫描线-区间加-区间历史min个数就ok了
也是俩log
第二类支配对
第一种是对每个 $i$, 可以用数据结构找出 $\log n$ 个 $j$ 支配了所有贡献, 此时分析 $i<j<k$ 中, $(i, k)$ 贡献需要不能被 $(i, j), (j, k)$ 取代
另一种是通过对一维分治, 会产生 $O(n)$ 对跨过分治中线的贡献, 支配了原来跨过中线的 $n^2$ 对. 此时一般对信息维/复杂的一维分治.
CF765F Souvenirs
经典之区间内绝对值最小的数对
就是对于 $i<j<k$, 若 $j$ 与其构成支配, 那么 $i, k$ 要想构成支配需要 $\vert i-k\vert\le \vert i-j\vert, \vert j-k\vert$, 发现每次把值域减半, 于是支配对只有 $n\log n$ 对.
CodeChef MINXORSEG
给定 $a_n$, $q$ 次问区间内最小的 $a_i \mathrm{xor} a_j$, 值域 $10^9$, $n, q\le 2\times 10^5$
仍然考虑 $i<j<k$, 假设 $i, j$ 支配. 考虑 $a_i, a_j, a_k$ 的lcp后的第一个字符 $c, d, e$
如果 $c=d\ne e$, 那么你选个锤子 $e$
如果 $c\ne d$, 那么 $e=c\ne d$ 相同, 不然 $a_k \mathrm{xor} a_j>a_k\mathrm{xor} a_i$, 应该选择 $j, k$.
于是惊喜的发现, 每次lcp增加至少1. 又只有 $n\log n$ 对了.
考虑如何找到它们, 建可持久化trie即可.
Luogu8078 [WC2022] 秃子酋长
区间内排序后相邻的数在原序列种位置的绝对值的差.
polylog!
对序列维分治, 那么设当前区间是 $[l, r]$, 中点为 $mid$
预处理 $[mid, x]$ 的答案, 是简单的.
假设排序后下标不跨过 $mid$ 的位置的差已经计算完了.
那么注意到, 对于左边两个数 $a_i<a_j$, 若存在 $a_k\in (a_i, a_j)$, 那么 $a_i, a_j$ 一定会贡献 $mid-i+mid-j$ 这样的. 如果中间没有, 则贡献 $i-j$
左边的数对中, 只有 $O(n)$ 对相邻对是有用的, 所以直接从左往右扫描, 维护相邻对, 注意到单次变化是 $O(1)$ 的, 得到所有的对. 然后对每个 $(i, j)$ 求最小的 $k$, 就会得到一个对询问 $(ql, qr)$ 的矩形贡献.
右边对左边的贡献同理.
因为每层有 $n$ 对, 一共 $\log n$ 层, 作矩形加单点查单次 $\log n$, 所以复杂度 $n\log^2 n+m\log n$
P9058 [Ynoi2004] rpmtdq
给定一棵有边权的无根树, 需要回答一些询问.
定义 $\texttt{dist(i, j)}$ 代表树上点 $i$ 和点 $j$ 之间的距离.
对于每一组询问, 会给出 $l, r$, 你需要输出 $\min(\texttt{dist(i, j)})$ 其中 $l\leq i < j \leq r$.
$n\le 2\times 10^5, q\le 10^6$
考虑树分治, 进行边分, 树变成左子树, $x\to y$, 右子树三部分.
那么对于点 $u$, 考虑 $dis(v, y)\le dis(u, x)$ 的点, 如果 $u<v<w$, 那么因为 $dis(v, w)\le dis(x, v)+dis(x, w) \le dis(u, x)+dis(x, v/w)$ 所以 $v, w$ 可以取代 $u, w$.
所以每个 $u$ 只和这个区域内的前驱和后继贡献. 按深度扫描一边, 处理另一边即可单log求出这线性对.
于是现在一共有 $n\log n$ 对, 每个贡献一个矩形, 问题解决
Luogu9062 [Ynoi2002] Adaptive Hsearch&Lsearch
有 $n$ 个点 $p_1, p_2, \dots, p_n$ 在二维平面上.
有 $q$ 次询问, 在第 $i$ 个询问中, 给定两个数 $l_i, r_i$ ($1\leq l_i< r_i\leq n$), 你需要找到一对 $(u, v)$ 满足 $l_i\leq u<v\leq r_i$, $p_u$ 和 $p_v$ 之间的欧几里得距离 $\sqrt{(x_u-x_v)^2+(y_u-y_v)^2}$ 最小.
$n, q\le 2. 5\times 10^5$
todo
倍增值域分块(分组)
CF702F T-Shirts
有 $n$ 种 T 恤, 每种有价格 $c_i$ 和品质 $q_i$.
有 $m$ 个人要买 T 恤, 第 $i$ 个人有 $v_i$ 元, 每人每次都会买一件能买得起的 $q_i$ 最大的 T 恤. 一个人只能买一种 T 恤一件, 所有人之间都是独立的.
问最后每个人买了多少件 T 恤? 如果有多个 $q_i$ 最大的 T 恤, 会从价格低的开始买.
$n, m\le 2\times 10^5$
转化成从大到小对每个衣服, 每次给所有买得起的人加一并减钱.
把 $v$ 排序, 如果能维护顺序就好做了, 注意到减并不改变相对顺序, 但 $[c, 2c]$ 的会和 $[0, c]$ 的归并, 而更大的不受影响.
于是做法出现: 每一次减的时候, 暴力改 $[c, 2c]$, $[2c, inf]$ 打标记, 这样暴力改的每个数都每次减半了.
[Ynoi2007] rgxsxrs
给定一个长为 $n$ 的序列 $a$, 需要实现 $m$ 次操作:
1 l r x: 表示将区间 $[l, r]$ 中所有 $>x$ 的元素减去 $x$.
2 l r: 表示询问区间 $[l, r]$ 的和, 最小值, 最大值.$n, m\le 5\times 10^5, a_i, x\le 10^9$
值域分块, 但第 $i$ 块大小是 $2^i$, 让第 $i$ 块是 $[l_i, r_i]$, 每个块开个东西维护.
如果这个 $l_i>x$, 那么直接打标记, 并把最后几个元素干到下一块.
如果 $x\in [l_i, r_i]$, 从上暴力往下遍历, 因为每个减了的都会到下一块(至少会减 $2^{i-1}$ )
最后查询的时候把每个块的”东西”查一遍. 俩log真的能过这东西吗?
lxl推荐把开一个线段树, 每个区间存区间内的每个”东西”的信息
[Ynoi Easy Round 2022] 堕天作战
给定一个长为 $n$ 的序列 $a$, 有两种操作, 共 $m$ 次:
- 给定 $l$ $r$ $x$, 对于所有 $i$ 满足 $l\le i\le r$ 且 $a_i \neq x$, $a_i\leftarrow a_i-x$.
- 给定 $l$ $r$, 求对于所有 $i$ 满足 $l\le i\le r$ 且 $a_i\neq 0$, $a_i$ 的和.
对于 $100%$ 的数据 $1\le n, m \le 5\times10^5, 0\le a_i, x \le10^9$.
仍然用上一题的办法, 只不过这次会给小于 $x$ 的也减了.
那么小于 $0$ 的数直接减, 大于 $0$ 的数一个一个的变成小于 $0$ 个数, 反正每个数只会跨过 $0$ 一次.
CF1515I Phoenix and Diamonds
$n$ 种钻石, 一颗第 $i$ 种钻石重量为 $w_i$, 价值为 $v_i$, 一开始第 $i$ 中钻石的库存为 $a_i$. 接下来进行 $m$ 次操作:
1 k d: 进货了 $k$ 个种类为 $d$ 的钻石;2 k d: 卖出了 $k$ 个种类为 $d$ 的钻石;3 c: 如果你有一个大小为 $c$ 的袋子, 且按照第一关键字为价值(从大到小), 第二关键字为重量(从小到大)的顺序取钻石的话, 你最终可以取到钻石的价值为多少(注意操作不会真正执行)$1\leq n\leq 2\times 10^5$, $1\leq m\leq 10^5$, $1\leq k, d, a_i\leq 10^5$, $1\leq c\leq 10^{18}$.
因为前两个操作, 考虑排序钻石的 $v$, 问题是解决询问.
考虑当前 $c$ 最高位是 $k$, 那么减一个大于 $2^k$ 的, 或一直减小于 $2^k$ 的元素直到减不动, 都让 $k-=1$
于是做法是对于当前的 $k$, 只考虑小于 $2^k$ 的元素, 在这些元素中二分就行了.
最后复杂度2log
loj #3527. 「IOI2021」地牢游戏
辣鸡loj不能复制md题面
对当前能力 $s$ 分组, 假设当前处于 $[2^k, 2^{k+1}]$
比这个区间小的一定赢, 大的一定输.
如果敌人能力是这个区间的, 并且赢了一定能让 $k$ 变大. 因此考虑第一次赢这个区间的敌人的时间, 注意到之前若碰到小于 $2^k$ 的直接赢, 大于的直接输, 所以预处理 $f_{u, i}, g_{u, i}$ 表示 $u$ 在这种情况下走 $2^i$ 步的值, 以及 $h_{u, i}$ 表示 $u$ 走 $2^i$ 步碰到的 $s-\Delta c$ 的最小值.
复杂度是倍增log+分组log.
[FJOI2016]神秘数
收录在ds中.
2019ICPC徐州 H - Yuuki and a problem
维护一个长为 $n$ 的序列 $a_i$, 有 $m$ 次操作:
- 单点修改
- 求区间中所有子集和的 $mex$
$a_i\le 10^9, n, m\le 10^5$
上一题加了单点修改. 但上一题俩log了已经, 换上树套树就3log寄了.
考虑把所有数按 $2^k$ 分组, 那么现在能表示的数最大在 $[2^k, 2^k+1]$ 则可以直接加底下的所有.
因为只要加一个当前组的数就可以进入下一组, 所以就能做了.
于是只要对每个组开个线段树, 维护区间和, 区间min即可.
减半警报器
处理的大概是, 维护若干个范围, 每次把包含一个点的都减掉一部分, 问每个什么时候到 $0$.
思路大概是, 拆分成若干更简单的(自由度更低)的范围, 每次一个被改没了就平摊到所有被拆分出来的. 这么做代价是log值域
CCPC2022 绵阳B CF gym 104065 B
猫树分治, 给前缀后缀做就成了前缀/后缀加了, 为了警报需要维护个最小值, 可以每层一个线段树, 每次修改 $log^2 n$, 平摊总代价是 $\log n \log v$
CF gym 102331 F. Fast Spanning Tree
给你一张有 $n$ 个点的图, 每个点有非负点权 $w_i$.
有 $m$ 个三元组 $(a_i, b_i, s_i)$, $a_i\ne b_i$, $s_i$ 非负
一直进行如下的操作:
如果没有 $i$ 满足: $a_i$ 和 $b_i$ 在图中的两个不同的连通块中, 且($a_i$ 所在连通块的 $w_i$ 和)+($b_i$ 所在连通块的 $w_i$ 和)$\ge$ $s_i$, 则停机
否则找到最小的满足条件的 $i$, 输出 $i$, 并且将 $a_i$ 和 $b_i$ 连通
相当于是 $m$ 条边. 不断加边.
把每条边权值划分到两个所在连通块中, 每个连通块开一个全局减和单点改, 找最小值的数据结构, 每次合并的时候给边减去一个什么东西, 就行了.
Codeforces gym 102452 I
啊, 就是直接把每个国家的分摊到三个观察点上, 每个观察点开一个数据结构能找最小值, 删最小值, 全局减就行了.
P7603 [THUPC2021] 鬼街
那条街有”鬼街”之称, 十年前是 A 市最繁华的地段之一, 然而如今这里已无活人居住.
街边七零八落地排着 $n$ 座房子, 每栋房子都有一个 $1$ 到 $n$ 之间的独一无二的编号, 用仿佛来自地狱的黑漆涂在破瓦残砖上, 在黄尘中隐隐若现.
传说, 这条街上的鬼是与别处的鬼是不同的, 它们喜欢研究数论, 会根据数字的性质来选择自己的生活, 所以它们才为每一栋房子都画上了编号.
新上任的 A 市市长并不相信魑魅魍魉的传言, 为了探清真相, 他决定为这条街装上灵异事件监控器.
下面有 $m$ 个事件依次发生.
- 灵异事件: 在以 $x$ 的所有质因子为编号的房子里, 都发生了 $y$ 次闹鬼. 由于神秘的原因, 次数 $y$ 可能为 $0$.
- 监控事件: 有一个监控器被安装, 其监控以 $x$ 的所有质因子为编号的房子, 当累计的闹鬼总次数达到阈值 $y$ 时, 该监控器会触发报警(若 $y = 0$, 则不论被监控的房子是哪几栋, 下一次灵异事件都会立即触发该监控器的报警). 不同房子发生的灵异事件次数会被分开统计, 不同的监控器互不影响. 所有的监控器被从 $1$ 开始依次编号.
请将所有的报警反馈给市长, 即每个灵异事件之后, 有哪些监控器被触发.
$n, m\le 10^5, x\le n, y\le 2^{32}$
每个监控器最多看六个房子, 每次最多给六个房子加 $y$.
剩下的和上个题没有区别.
感觉这类题知道套路后有点套路.
杂题选讲
sqy讲课
是杂题选讲
