ZROI省选集训
Day1 数据结构
rprmq1
分治+同一分治深度的一起处理+扫描线+区间历史最大值, 参见sdjx1
P8512 [Ynoi Easy Round 2021] TEST_152
转转有一个操作序列 $(l_i, r_i, v_i)$.
现在, 有 $q$ 个询问 $l$, $r$.
每次询问, 你初始有一个长度为 $m$ 的序列 $c$, 初值全是 $0$.
现在我们从 $l$ 到 $r$ 执行这 $r-l+1$ 个操作.
每个操作是将 $c[l_i]$ ~ $c[r_i]$ 赋值为 $v_i$.
询问所有操作结束后整个 $c$ 的序列所有数的和.
询问之间互相独立.
$n, q\le 5\times 10^5$
考虑扫描线, 看出扫序列没前途, 于是扫操作.
那么扫描操作维 $r$, 过程中珂朵莉树维护序列维, 并在珂朵莉树每个节点上维护其插入时间 $t$, 对某个 $r$, 每个节点的贡献就成了当 $l>t$ 时答案加上 $sum$.
注意此时珂朵莉树不会真删而是加入一个贡献 $-sum$ 的(理所当然)
于是在珂朵莉树维护的同时用一个树状数组维护在这个时刻后的连续段之和, 是一个后缀和.
复杂度是单log.
P8337 [Ynoi2004] rsxc
给定一个长为 $n$($1\le n\le 6\times 10^5$)的非负整数序列 $a_0, a_1, \dots, a_{n-1}$($0\le a_i<2^{30}$).
有 $q$ 个询问($1\le q\le 10^6$).
每次询问给出两个整数 $l, r$($0\le l\le r<n$), 求有多少对整数 $(x, y)$ 满足:
- $l\le x\le y\le r$;
- $\forall i, j\in S\ : i\oplus j\in S$, 其中 $S: ={a_k}_{k=x}^y$.
$n, q\le 10^6$
区间线性基:
扫描线扫 $r$, 线性基中每个位置再维护一下这个数的下标, 使得每个位置是最靠右的使这一位为 $1$ 的位置.
于是 $[l, r]$ 的线性基就是这个线性基中所有下标大于 $l$ 的部分构成的.
于是考虑枚举 $\vert S\vert$(显然只有 $\log n$ 种), 然后确定大小之后双指针. 某个区间满足条件当且仅当其 $\vert S\vert$ 为 $2^{\vert V\vert}$, $V$ 为线性基. 这样就能解决全局了.
对于区间询问, 每个 $\vert S\vert$ 大小分别处理, 那么此时一个 $r$ 对应一个区间的 $l$, 且这个区间左右端点分别递增. 这个可以线性预处理常数查询.
P8265 [Ynoi Easy Round 2020] TEST_63
定义一条链的权值是链上所有点编号的异或和, 维护一个森林, 支持加边, 删边, 查询森林中所有树上的所有重链放到一起, 权值的第 $k$ 小. 如果一个点有多个子树大小最大的儿子, 取其中编号最大的. 加边的时候新树的根改为第二个操作点, 删边的时候深度更大的点自动成为新树的根. $n\leq 10^5, m\leq 5\times 10^5$, 时限5s.
对每个点维护重儿子, 最大轻儿子, 对每个重链开一个平衡树.
那么对于换根, 可以对当前点到根上的每个重链分别翻转, 所有轻边也换方向, 因为路径上经过的重链只有 $\log n$ 条所以没问题.
此时重儿子变化情况有三种:
- 重儿子变父亲, 父亲变重儿子:
- 因为翻转了这个重链, 所以不用管
- 重儿子变轻儿子, 父亲变重儿子:
- 表示出来是 $siz_fa>siz_weightest>siz_max$, 这种只有 $\log n$ 个, 可以二分出来.
- 重儿子变父亲, 轻儿子变重儿子:
- 同上一个
而link只要先把两个节点都换成根, 然后更新其中的一个重儿子.
cut $u, v$ 把 $u$ 变成根, 断掉之后更新重儿子.
查询可以开一个平衡树维护所有重链.
[Ynoi2009] pmrllcsrms
给你一个长度为 $n$ 的整数序列 $a$, 和一个常数 $c$ .
有 $m$ 次操作:
1 x y: 将位置 $x$ 的值修改为 $y$.
2 l r: 表示询问区间 $[l, r]$ 中 $\max\left(\max_{l \leq l’ \leq r’ \leq r\atop r’-l’+1\leq c} ~~ \left(\sum_{i=l’} ^{r’} a_i\right), 0\right)$.
$n, m\le 2\times 10^6$
考虑以 $c$ 为大小分块, 那么一块内的是最大子段和, 此时问题就变成了处理一个前缀和一个后缀拼起来的.
对于两个块之间的, 相当于是一个平面下, 找到平行于二四角平分线斜线下的一个三角形下权值最大的点.
此时可以把横轴翻转, 于是斜线变成一三象限角平分线, 问题变成了找最大的 $a_x+b_y, 1\le x\le y\le c$. 这个可以直接线段树维护.
此时单点改是显然的(一个区间加). 复杂度最后是1 $\log n$.
[Ynoi2010] y-fast trie
给定一个常数 $C$, 你需要维护一个集合 $S$, 支持 $n$ 次操作:
- 操作1: 给出 $x$, 插入一个元素 $x$, 保证之前集合中没有 $x$ 这个元素
- 操作2: 给出 $x$, 删除一个元素 $x$, 保证之前集合中存在 $x$ 这个元素
每次操作结束后, 需要输出 $\max\limits_{\substack{ i, j \in S \ i \ne j }} \bigl( (i+j) \bmod C \bigr)$, 即从 $S$ 集合中选出两个不同的元素, 其的和 $\bmod~C$ 的最大值, 如果 $S$ 集合中不足两个元素, 则输出
EE.本题强制在线.
$n\le 5\times 10^5$
128m
和上一个题很类似.
$\mod C$ 之后答案是 $\max a+b-C$, 或者 $\max a+b, a+b<C$, 而后面这个把一维反转, 区别在于修改变成了插入删除. 此时就是求全局最近的前驱, map维护前驱, 修改时常数次更新.
P6018 [Ynoi2010] Fusion tree
给定 $Tree(n)$, 点有权值 $a_i$, $m$ 次操作, 每次对与 $u$ 距离为 $1$ 的点加1, 对 $u$ 减 $v$ 或询问与一个点 $x$ 距离为 $1$ 的所有节点的权值异或和.
$n, m\le 5\times 10^5$
每个点开一个动态开点01trie, 支持全局加一和单点改, 维护所有儿子.
全局加一可以考虑, 从低位到高位建, 对于一个当前的加一, 左子树右子树交换, 然后要接着递归到交换后的左子树下面去即可. 这个过程维护一个异或和是简单的.
复杂度1log
P8336 [Ynoi2004] 2stmst
已知 $n$ 个顶点的有根树, 以及 $m$ 个二元组 $(x_i, y_i)$, 其中 $x_i, y_i$ 是树的顶点.
对于树的顶点 $a, b$, 定义 $D(a, b)$ 为: 在以 $a$ 为根的子树中, 但不在以 $b$ 为根的子树中的顶点个数.
你需要求出以这些二元组为顶点的完全图的最小生成树, 其中 $(x_i, y_i)$ 和 $(x_j, y_j)$ 之间的边权是 $D(x_i, x_j)+D(x_j, x_i)+D(y_i, y_j)+D(y_j, y_i)$.
对于 $100%$ 的数据, 满足 $1\le n\le 10^6, 1\le m\le 10^5$. 对任意 $i=1, 2, \dots n-1$, 满足 $1\le f_{i+1}<i+1$. 对任意 $i=1, 2, \dots m$, 满足 $1\le x_i, y_i\le n$.
考虑brovka.
$D(a, b)+D(b, a)$ 表示, 若 $a, b$ 有祖先关系就是 $\vert siz_a-siz_b\vert$, 否则是 $siz_a+siz_b$.
于是要统计答案, $x$ 没有祖先关系的可以直接看成任意两 $x$ 之和, 然后再去算 $y$ 的即可($y$ 的子树内和 $y$ 子树外分别处理). 这部分是线性的. $y$ 没有的同理, 于是问题变成了两者都有祖先关系的情况.
这种情况你就分若干类讨论, 如果 $x_i, y_i$ 都是作为祖先的, 可以用线段树合并维护做到1log, 实际看起来是个二维数点.
如果不都作为祖先, 比如 $x$ 作为祖先, 那么dfs这棵树, 遇到一个 $x_i$ 的时候就在 $y_i$ 处单点改, 遇到一个 $x_j$ 要查它到根的最小值即可.
todo
[Ynoi2003] 博丽灵梦
矩形颜色数, 带权.
给定一个有 $n$ 个点的二维平面, 每个点坐标为 $(i, p_i)$ , 其有权值 $a$.
给定一个长为 $n$ 的数组 $b$, 其下标从 $1$ 到 $n$.
有 $m$ 次查询, 每次查询给定一个矩形 $l_1, r_1, l_2, r_2$, 定义集合 $S={a_i \vert l_1\le i\le r_1 \land l_2\le p_i\le r_2}$, 求对于集合 $S$ 中所有元素 $j$, $b_j$ 的和.
对于所有测试点: $2 \leq n \leq 10^5$, $1 \leq m \leq 10^6$, $1 \leq l_1\le r_1 \leq n$, $1 \leq l_2\le r_2 \leq n$, 保证 $p_i$ 为一个排列, 保证 $1\le p_i, a_i, b_i\le n$.
莫队做 $l_1, r_1$, 在 $l_2, r_2$ 这一维做待修区间数颜色复杂度根号2log.
考虑优化区间数颜色, 问题变成了
- 莫队时要查询前驱后继: 容易回滚莫队+每个颜色开链表解决(2022WC秃子酋长)
- $m$ 次矩形查, $n\sqrt m$ 次单点加. 考虑二维分块, 先按 $B=n^{\dfrac{3}{4}}$ 分块, 每个块再按 $C=\sqrt n$ 分块, 此时查询一个2side矩形时, 每一维会拆成 $n^{0. 25}$ 个大块和 $n^{0. 25}$ 个小块, 发现直接加入所有这样的块的复杂度就是 $\sqrt n$. 而对于修改, 只有所在的四个块要改(四个块分别是两边边长为 $B$ 或 $C$ 的两种). 最后问题是散块, 查询时直接枚举一维, 判断对应的最多 $O(1)$ 个另一维是否有值即可($O(1)$ 说的是每个 $i$ 只对应一个 $last_i$, 每个 $last_i$ 也只对应一个 $i$, 任意时刻点集都是一一对应的).
P8419 [THUPC2022 决赛] riapq
给出排列 $a_1, \dots, a_n$, 你需要维护序列 $b_1, \dots, b_n$, 初值为 $0$.
共 $m$ 次操作:
修改操作: 给出 $l, r$, 对每个 $(i, j)$ 满足 $l\le i\le j\le r, ; a_i\le a_j$, 将 $b_j$ 增加 $1$;
查询操作: 给出 $x$, 查 $b_x$.
对于 $100%$ 的数据, 满足
$1\le n, m\le 2\times 10^5$;
$1\le a_i\le n$, $a_i$ 互不相同;
$1\le l\le r\le n$;
$1\le x\le n$.
尝试操作分块, 失败.
把修改差分. 变成两部分, 其中 $[1, i-1]$ 对 $i$ 的贡献预处理.
还要去掉 $[1, l-1]$ 对 $i$ 的贡献, 考虑前 $j$ 个块对 $i$ 的贡献, 可以预处理后 $\sqrt n$ 查.
已经完成的这部分可以修改的时候直接打标记.
现在问题是 $[1, l-1]$ 剩下的散块对 $[l, r]$ 的贡献, 散块里面每个数相当于一个矩形加, 成了 $n\sqrt n$ 个矩形加, 线性个单点查, 把加和查对偶, 然后就成了 $n$ 次矩形加, $n\sqrt n$ 次查, 此时的性质是同一个散块贡献的时候横坐标对应的 $[l, r]$ 相同, 纵坐标是不同的后缀.
todo
[Ynoi2003] 樋口円香
给定两个序列 $a_1, \dots, a_n$, $b_1, \dots, b_n$, 一开始 $b_i=0$;
你需要进行 $m$ 次操作:
每次操作, 给出 $l, r, L$, 需要对于 $k\in[l, r]$, 将 $b_{L+k-l}$ 增加 $a_k$;
最后输出经过所有操作后的序列 $b_1, \dots, b_n$.
对于 $100%$ 的数据 $0\le a_i\le 1000$; $1\le n\le 10^5$; $1\le m\le 10^6$.
考虑对 $a$ 分块, 散块直接暴力加, 离线后单独考虑每个块 $c$, 卷上 $d$, 其中 $d_k$ 为 $L=k$ 的个数.
最后平衡一下可以把 $\log$ 放到根号下面, 复杂度 $n\sqrt{q\log n}$.
[Ynoi2078] 阅读报告(更新中. . . )
给定序列 $a_1, \dots, a_n$, 共 $m$ 次询问, 每次询问给出 $l, r$, 查询所有满足 $l\le L\le R\le r$ 的 $(L, R)$ 的权值的按位异或和, 二元组 $(L, R)$ 的权值是 $\vert {a_i\mid L\le i\le R}\vert$.
对于 $100%$ 的数据, 满足 $1\le n, m\le 4\times 10^5$, $1\le a_i\le n$, 所有数值为整数.
考虑对 $r$ 扫描线, 维护 $a_l$ 表示 $l$ 到 $r$ 的颜色数, $b_l$ 表示 $[l, l]\mathrm{xor}[l, l+1]\ldots\mathrm{xor}[l, r]$, 问题变成了 $b_i\to b_i\mathrm{xor}a_i$, 查区间 $b_i$ 异或和, $a$ 区间加 $1$.
考虑分块, 再定义一个参数 $B$, 维护整块加标记, 整块异或 $a_i+x$ 标记(一个 $x$ 的集合), $a_i+x$ 的异或和, 对 $x\le B$, 以及整块 $b$ 异或和.
每次对 $a$ 区间加就整块标记散块暴力+重构, 对 $b$ 异或 $a$ 就整块标记散块暴力+重构, 区间查同理, 然后每当加法标记 $>B$ 就重构. 显然重构次数线性, 问题就是如何重构.
重构一个块的时候:
- 考虑如何维护 $a_i+x$ 的异或和, $x\le \sqrt n$
- 传统 $trick$ 逐位考虑 $a_i+x$ 的第 $k$ 位表示对应位相加, 再加上前 $k-1$ 位加起来是否到能进位.
- 于是要求所有的前 $k-1$ 位相加进位的个数
- 注意到, 若 $2^{k-1}\ge \sqrt n$, 它就只有 $k-1$ 位, 这些可以直接处理.
- 而对于不到 $n$ 的那些 $k$, 可以直接枚举所有值求个数.
- todo
- 还原 $b$ 的部分是对称的.
[Ynoi2007] tmpq
给定三个长为 $n$ 的数组 $a, b, c$, 满足 $1\le a_i, b_i, c_i\le n$ 且为整数.
你需要进行 $m$ 次操作, 每次操作为:
1 k x: 代表将 $a$ 序列的第 $k$ 个位置改为 $x$, 即 $a_k : = x$.
2 r: 代表查询有多少个三元组 $(i, j, k)$, 满足 $1\le i<j<k\le r$, 且 $b_{a_i}=a_j=c_{a_k}$.对于 $100%$ 的数据, 满足 $1\le n\le 2\times 10^5$, $1\le m\le 5 \times 10^4$, $1\le a_i, b_i, c_i, x, k, r\le n$.
实际上 $b_{a_i}$ 和 $c_{a_k}$ 并没有什么性质, 直接当成单点修改 $a, b, c$, 然后问 $b_i=a_j=c_k, i\le j\le k$.
对出现次数根号分治:
对于大于 $\sqrt n$ 的部分, 对每个颜色维护一个动态dp, $f_{p, 0/1/2}$ 表示位置 $p$ 左边已经有了 $1/2/3$ 个数对(比如 $2$ 表示 $b_i=a_j$ 的对数), 那么转移可以写成矩阵, 就成了单点改前缀矩阵乘积.
对于小于 $\sqrt n$ 的部分, 修改的时候暴力处理这个颜色的dp, 然后每个位置贡献到一个后缀.
UOJ#712. [北大集训2021]简单数据结构
给定 $a_n$, 全局 $a_i+=i$, 全局取min, 区间求和.
$n, q\le 2\times 10^5$
考虑经过取min之后的点, 注意到如果先取min $v$ 再加 $i$ 等价于先加 $i$ 再取min $v+i$.
于是对于某一个时刻, 取min之后的点是单调的: 每个取min都是 $i$ 对 $v+ki$ 取min.
于是是若干条直线得到一个上凸包, 每次取min会把凸包上方的移动到凸包上.
于是分开维护, 那么凸包上的点线段树维护, 凸包下面的也是.
最后差的一步就是整体二分求所有点到凸包上的时间.
UOJ#715. [北大集训2021]小明的树
小明有一棵以 $1$ 为根的 $n$ 个节点的树, 树上每一个非根节点上有一盏灯, 他有一个 $2\ldots n$ 的排列 $a_{n-1}$. 他还有一个计数器, 初始为 $0$.
他会按照排列依次点亮这 $n−1$ 盏灯, 每进行一次点灯操作后, 他会检查整个树是否是美丽的, 如果是美丽的, 计数器会加上此时点灯的节点形成的联通块的个数.
$n−1$ 次点灯后计数器的值, 记为这棵树的答案.
一个树是美丽的当前仅当对于每一个被点亮的节点, 这个节点子树内的节点都是点亮的.
小明认为这个问题太简单了, 他觉得应该让树动起来.
在初始查询后, 他会删掉树中一条边并加上一条边, 保证修改后还是一棵树, 他想知道每一次修改后将计数器清零后重新点灯并计数, 这棵树的答案是多少.
$n, m\le 5\times 10^5$
美丽的条件是未点亮的部分是一个连通块.
维护前缀, 后缀的点减边 $a_i, b_i$.
那么每条边的变化都是区间加减.
同时显然点减边最小为 $1$, 所以就维护所有 $a_i$ 为最小值的位置的 $b_i$ 的和即可.
todo 月球列车
Day2 数数
Agc060c
对所有的 $p_{2^n-1}$, 要求满足 $P_i<P_{2i}, P_i<P_{2i+1}$ 中, 给定 $a, b$, 求随机一个满足条件的排列 $P_{u=2^a}>P_{v=2^{b+1}-1}$ 的概率.
$n\le 5000$
$u, v$ 分别是 $a, b$ 层最左边和最右边的点.
考虑总数:
[trick] $n! \times \prod_i \dfrac{1}{siz_i}$
可以直接考虑从上到下对于每个子树根是其最小值.
考虑对最左链和最右链归并, 树的形态变成一条链, 链除了第一个(根)和两条链的末尾以外每个点都挂了一个子树, 于是问题就变成了最后一个点是左边的还是右边的.
然后直接对这条链dp, 每个子树的方案数已经确定, $f_{i, j, 0/1}$ 表示前 $i$ 个点, 选了 $j$ 个左边的点, 最后一个是左边/右边的方案数.
Agc060d
给定 $n$, 求有多少个排列对 $p, q$, 满足对于每个 $i$, $p_i, q_i$ 分别大于或分别小于 $p_{i+1}, q_{i+1}$.
$n\le 2\times 10^5$
考虑枚举一个大于号集合 $S$, 方案数变成
$$
\begin{aligned}
&\sum_S (\text{大于号集合为S的方案数})^2\
=&\sum_S (\sum_{T\supseteq S}(-1)^{\vert T\vert-\vert S\vert}\text{大于号集合}\supseteq \text{T个数})^2&&\text{子集反演}\
=&\sum_S \sum_{T_1, T_2, S\subseteq T_1, T_2} (-1)^{\vert T_1\vert +\vert T_2\vert }(\text{大于号集合} \supseteq T_1)(\text{大于号集合}\supseteq T_2)\
=&\sum_{T_1, T_2} (-1)^{\vert T_1\vert+\vert T_2\vert}(\text{大于号集合}\supseteq T_1)(\text{大于号集合}\supseteq T_2)\times 2^{T_1\cap T_2}&&\text{传统艺能交换求和号干掉S}\
\end{aligned}
$$
其中, $T_1\cap T_2=T_1+T_2-T_1\cup T_2=T_1+T_2-(n-1)+(T_1, T_2\text{同时不包含的元素个数}$), 而最后一部分的意思就是两个序列再某个位置都不是大于号.
而考虑到, 大于号集合包含于 $T$ 的个数可以看成, 被钦定的大于号连成若干个递减段, 假设长度是 $l_1\ldots l_k$, 那就是 $\dfrac{n! }{\prod_i l_i! }$(每一段内部递减).
于是式子变成了
$$
2^{-n+1}\sum_{T_1, T_2}((-2)^{T_1}\dfrac{n! }{\prod l_{1, i}! })((-2)^{T_2}\dfrac{n! }{\prod l_{2, i}! })\times 2^{T_1, T_2\text{同时不包含的个数}}
$$
现在只有最后一小部分不独立, 考虑同时不包含, 也就是同时为小于, 把序列分成若干段, 每一段独立.
把每一段的贡献记作 $2[x^{len}]F(x)=\sum_{T_1, T_2}2((-2)^{T_1}\dfrac{1}{\prod l_{1, i}! })((-2)^{T_2}\dfrac{1}{\prod l_{2, i}! })$, 最后乘一个 $\dfrac{1}{2}$, 就消掉了最后那个不独立的项. 答案就成了 $2^{-n+1}(n! )^2\dfrac{1}{2}\dfrac{1}{1-2F}$
于是只要考虑求 $F$, 这个 $F$ 要求不能有某个位置 $T_1, T_2$ 同时为小于, 考虑忽略这个限制的生成函数 $G$, 那么因为此时 $T_1, T_2$ 独立, $[x^k]G(x)=(\sum_T (-2)^T \dfrac{1}{\prod l_i})^2$, 再按照分成若干个连续的大于号段, 长 $i$ 的段贡献 $-\dfrac{1}{2}\dfrac{x^i}{i! }$, 所以一段就是 $-\dfrac{1}{2}e^x$, $G$ 就是把这些段卷起来, 然后 $x^i$ 再乘上 $(-2)^{i+1}$, 再把每个系数平方.
然后要求 $F$, 发现一个 $G$ 可以在第一个同时为小于的地方断出一个 $F$, 而后面可以是一个 $G$ 或者什么都没有, 于是 $G=F(G+1)$, 就可以根据 $G$ 求个逆求 $F$ 了.
于是就做完了.
Agc059c
实际上等价于每个三元组 $(x, y, z)$, 最后问 $x, z$, 满足 $y$ 是三者之间的最大值或最小值.
以二元组 $(x, y, </>)$ 作为点表示 $x<y$, $x>y$, 对每个三元组在其中连边. 这样形成若干个连通块, 每个连通块内相互等价, 然后就二的(连通块个数/2)次方, 无解当 $(x, y, >)$ 和 $(x, y, <)$ 等价.
Agc054c
考虑 $P$ 变成 $P’$ 的过程, 我们一定可以找到一个位置 $i$ 满足有大于 $k$ 个大于 $P_{i+1}$ 且 $P_i>P_{i+1}$, 然后进行一次, 于是最小次数就是 $\sum_i \max(0, x_i-k)$, 所以最后的排列和交换过程都是唯一的.
于是, 如果一个元素前只有小于 $k$ 个大于它的则它一定没有被swap过.
考虑所有等于 $k$ 的, 递增的子序列, 它可以放在以后的任意一个位置, 因为这些元素的后面的元素必然都大于它.
于是直接拿着个算答案即可.
Agc043d
若最终排列中有 $p_i>p_{i+1}$, 显然这两个元素一开始在同一个块里.
于是用前缀max划分这个序列成若干段, 要求每一段长度不超过3.
于是长度为 $2$ 的段的个数要小于等于长度为 $1$ 的, 不然无法都凑成长度为 $1$ 的段.
发现充要了.
然后用这个计数, 枚举长 $1$ 和长 $2$ 的个数 $n_1, n_2$, 得到 $n_3$, 答案就是
$$
\dfrac{(3n)! }{(3! )^{n_3}(2! )^{n_2}(1! )^{n_1}}2^{n_3}
$$
或者直接dp
Agc039e
注意如果有一个X, 则X的对边不能连线.
于是对于一个连线 $a\to b$, 只有恰好一个点可以连出这个区间 $a, b$.
于是 $f_{l, r, x}$ 表示 $[l, r]$ 中只有 $x$ 连出了这个区间.
转移就是, 枚举一条跨过 $x$ 的边 $i\to j$, 其中 $j$ 是最后一个有跨过 $x$ 边的点, 它和 $x$ 的边形成一个X, 然后一定存在 $i, x$ 和 $x, j$ 中间的两个点 $p, q$ 将整个 $[l, r]$ 分成三段, 三段内部自己匹配, 于是就可以从 $f_{l, p, i}, f_{p, q, x}, f_{q, r, j}$ 转移
Agc036f
如果把 $(i, p_i)$ 画出来, 相当于选距离原点大于 $n$, 小于 $2n$ 的点, 也就是两个圆之间, 并要求每一列, 每一行恰好放一个.
然后考虑如果只有上界, 也就是外面的圆, 问题是好做的: 把所有上界 $a_n$ 递增排序, 答案就是 $\prod_i a_i-i+1$.
于是容斥下界, 枚举容斥集合大小 $k$, 那么现在要求左边的 $n$ 列中有 $k$ 个上界为小圆 $b_i$, 剩下的其他 $2n-k$ 列上界为大圆 $a_i$ 的方案数, 考虑从下往上按上界(如果有小圆, 看小圆上界)从小到大dp, $f_{i, j}$ 表示dp了前 $i$ 列, 其中有 $j$ 列是容斥集合中的, 直接转移即可. 复杂度 $n^3$
Agc035e
在黑板上写有 $-10^{18}$ 到 $10^{18}$ 中的所有整数, 每次你可以选中一个 $[ 1 , N]$ 中还在黑板上的整数 $x$, 把它擦去并补写上 $x − 2$ 与 $x + c$(如果原来不存在的话). 你可以进行这个操作任意次(可以不进行), 求最终黑板上数字的可能状态有多少种, 答案对 $M$ 取模.
$1\leq c \leq N \leq 150 , 10^8\leq M\leq 10^9$
首先肯定是转化成删掉的集合有多少种.
然后考虑一个集合什么情况下可以被删掉, 若建图, $i\to i-2, i\to i+c$, 则一个集合可以被删掉当且仅当导出子图无环(显然).
考虑如果 $c$ 是偶数, 那么奇偶独立, 显然对于奇偶分别做无环就是不能选长 $\dfrac{c}{2}$ 的连续段, 其他任意的方案数. 可以简单dp.
而如果是奇数, 发现此时这个环一定是先 $-2$, 再 $+c$, 再 $-2$, 再 $+c$ 成环, 其中恰好包含两个 $+c$. 考虑从小到大dp的过程中如何判断出环, 如果 $i$ 进行 $-2$, $+c$, $-2$ 后跳到的位置小于等于 $i+1-c$, 那状态不合法, 于是记录这个跳到的位置 $j$, 再记录一个 $i-1$ 这么跳到的位置 $k$, 这个 $j$ 和 $k$ 同时表示如果 $i/i-1$ 不能跳到一个可以 $+c$ 后仍然小于 $i/i-1$ 的位置, 那么就是光减2能到的位置.
另一个理解方式是把奇数偶数排成两条竖向下的链, 其中 $i$ 和 $i+c$ 对齐为同一层, 那么注意到环的长度一定是 $c+2$, 于是 $i$ 记录 $+2, -c, +2$ 后的长度 $j$, 以及偶数列向上连续选了多长 $k$, 状态合法当且仅当 $j<c$.
复杂度都是 $n^3$ 的.
Agc035d
设 $f_{l, r, x, y}$ 表示删掉 $l+1\ldots r-1$, 使得结束后 $xa_l+ya_r$ 最小.
转移就是枚举中间的数, $f_{l, r, x, y}=f_{l, p, x, x+y}+dp_{p, r, x+y, x}+(x+y)a_p$, 复杂度是 $2^npoly(n)$
Agc034f
dp表示成集合幂级数, 然后FWT多项式科技解出来
todo
Agc032e
当一个0变成1的时候, 其左右一定恰好一个0一个1
于是, 实际上翻转01只是移动01的分界线, 而起始处和结尾处存着一堆分界线.
容易发现两个局面就是给分界线匹配然后对应移动过去.
因为本质不同的匹配分界线的方案数只有 $O(n)$ 种, 再加上计算代价, 复杂度就是 $n^2$ 了.
某CTT题
dp+高斯消元, 设 $f_u(x)$ 表示当前在 $u$, 当前权值是 $x$, 到 $u$ 的期望权值是多少, 归纳发现 $f$ 是一次函数, 同理得到平方的期望的 $f$ 是一个二次函数, 于是列出递推式高斯消元.
另一个CTT题
todo
qoj5169
预处理在第 $i$ 家店花 $j$ 元钱的方式, 为 $[x^j]F_i(x)$, 这个就是每个娃娃机的卷起来, 也就是
$$
\prod_k \dfrac{1-x^{(c_{i, j}+1)b_{i, j}}}{1-x}
$$
卷起来即可.
于是在某一家店至少花 $k$ 元就要截取 $F$ 的一部分算.
每次询问卷积过于困难, 考虑点值.
todo
qoj5089
可以环覆盖的意思是每个点度数是偶数.
假设把所有点度数奇偶性状压成一个数, 则选一条边就是异或上 $2^x+2^y$.
todo
qoj5097
todo
Day3 模拟
A 计算几何科技
平面上有 $n$ 个互不相交的矩形, 求是否存在一条直线与所有矩形相交.
$n\le 2\times 10^5$
特判斜率为 $0$ 的情况, 考虑如果斜率为正, 那么直线一定把矩形的左上端点和右下端点分开了, 于是对每个矩形的左上, 右下分别求凸包判断两凸包是否有交即可.
另一个做法是考虑直线 $y=kx+b$, 对 $k$ 正负讨论之后, 可以根据每个矩形列出 $b$ 关于 $k$ 的不等式, 然后用ZJOI射箭的方法用半平面交解.
B 图论科技
给定平面上 $n$ 个黑点和 $n$ 个白点, 你需要将其两两匹配, 使得曼哈顿距离和最大.
把曼哈顿距离转化成切比雪夫距离, 把绝对值展开成 $\max$ 并拆开嵌套的 $\max$, 对于白点 $i$ 和黑点 $j$, 距离变成了 $\max(x_i-x_j, y_i-y_j, x_j-x_i, y_j-y_i)$ 四种. 因为是最大化的情况下拆开, 所以实质上是为每一个匹配任意选择这四种贡献方式中的一种, 再拆开就是为每个点任意选择四种贡献方式的一种, 并要求贡献 $x_i$ 的白点和贡献 $-x_j$ 的黑点数量, 和其他数量同理对应相同.
此时一个容易想到的做法是费用流, 结构是源点-白点-代表四种贡献的四个点-黑点-汇点, 就满足了这个条件.
于是想到模拟费用流, 那么一条增广路就是源点开始到某个颜色的点, 某个颜色的点经过黑点/白点到另一个颜色的点, 某个颜色的点到汇点三部分, 因为增广路不会走环, 于是路径只有 $poly(4)=O(1)$ 种, 直接对刚才增广路的三个部分分别开set动态维护, 复杂度是 $n\log n$
C 字符串科技
todo
