二轮省集
二轮省集
Day1
模拟赛
A.
数 $1\ldots 10^L$ 内有多少个数满足, 通过每次删三个连续且相同的数位可以删空($\texttt{011100}\to \texttt{000}$)
$L\le 10^7$
提前几个观察: 前导 $0$ 不重要, 只要不管然后乘 $\dfrac{9}{10}$ 即可.
考虑建树, 容易发现对于一个序列, 可以建一棵树, 每三个匹配的作为一个节点, 两个空隙往下连儿子, 于是设树的GF是 $T(x)$, 最后长恰好 $3n$ 的串个数就是 $[x^n]\dfrac{1}{1-10T(x)}$, 答案就是 $[x^n]\dfrac{9}{10(1-x)}\dfrac{1}{1-10T(x)}$, 显然有 $T(x)=\dfrac{x}{(1-9T(x))^2}$, 于是想到设 $T$ 的复合逆是 $R(x)$, 代入得 $x=\dfrac{R(x)}{(1-9T(x))^2}$, 拉反有 $[x^n]T(x)=\dfrac{1}{n}[x^{n-1}]\left(\dfrac{x}{R(x)}\right)^n=\dfrac{1}{n}[x^{n-1}]\dfrac{1}{(1-9x)^{2n}}$.
然后其实在列方程那步就知道这是微分有限的了, 高斯消元复杂度线性. 到这里之后可以列出 $\dfrac{1}{n}[x^{2n}y^{2n}]\dfrac{x^2}{1-\dfrac{1}{(1-9x^2)y}}$, 于是根据EI结论二元GF对角线是整式递推.
然后你就真的开始高消, 然后这里有个很大的坑, 对整式递推时因为所有系数都是 $0$ 总是一组解, 所以你会钦定一些东西为 $1$, 然后这里我设总和为 $1$, 然后发现总是解不出来, 因为这个题递推式系数和总是 $0$. 反正就是如果解不出来就是归一系数错了.
B.
称一个排列合法当且仅当按任意顺序操作每个 $i$ 至多一次使得排列升序, 操作是交换 $i, i+1$. 求所有的 $f_{i, j}$ 表示有 $j$ 个 $k$ 满足 $\vert k-a_k\vert=i$ 本质不同的合法序列.
做到 $n^2\log n$
/bx/bx/bx dwt
考虑置换环, 则不容易发现对于任意一个环一定是占据整个一个区间, 并且一定是先从左往右跳再从右往左跳. 证明归纳.
二项式反演, 钦定有 $i$ 个边跨度为 $k$, 记往左连的边是 $0$, 往右的是 $1$, $0\to 0, 1\to 1$ 只能在头/尾出现, $0\to 1, 1\to 0$ 只在一个环的头尾出现. 于是发现两个钦定的边的交的长度不超过 $2$.
于是考虑dp, 设 $f_{i, j}$ 表示前 $i$ 个点, 钦定了 $j$ 条边, dwt说转移有很多细节.
考虑复杂度, 发现 $j\le \dfrac{i}{k-1}$, 复杂度 $n^2\log n$.
C.
/bx/bx/bx zyz
给一棵有根树, 点 $i$ 上有值 $a_i$, 你可以按照 $1\ldots n$ 的顺序, 每次交换点 $i$ 和一个子树内的点上的 $a$, 使得 $a_i=i$, 构造方案或判断无解.
$n\le 5\times 10^5$
连边 $a_i\to i$ 表示 $a_i$ 要到 $i$, 考虑置换环/fn, 容易发现置换环不在一条链上无解. 此外考虑同一条链上, 则一个置换环上除了深度最低点都可以操作, 而一个 $n$ 点的置换环会拆成 $n-1$ 个二阶置换, 意味着所有点都要能操作, 于是进行一次交换后必须要满足交换后这个点为环内最低点, 于是应该是顺着走到第一个比当前点低的点交换. 于是写数据结构(zyz写了启发式分裂, 或者可以写平衡树)维护这个东西即可.
树上问题
Qoj8547 Whose Land?
扫描线, 每个点维护编号最大的特殊点编号, 问题变成邻域赋值/查询全局编号大于某值的个数, 则按照bfs序编号, 显然每个邻域操作拆出 $k$ 个bfs序区间贡献(每个深度), 于是颜色段均摊+BIT即可. 复杂度 $(nk+q)\log n$
[trick] 一个点到一个点集的距离最小值在dfn的前驱/后继取到.
CF1610H Squid Game
dwt秒3100
链的话扫描线+贪心, 尽量在右边选即可.
对于树, 从下往上走, 对于祖孙链最晚肯定是在祖先在链上的儿子处删, 不断重复着贪心, 用bit+dfs序维护, 而发现若以第一次操作的点为根, 则树上就只剩下祖孙链了.
考虑随便一个点为根跑刚才的做法, 发现对于非祖孙链, 往上的点一定比往下的优, 而上面做法找到的解满足每个点深度都最小, 所以此时一定需要再操作一次, 在根处即可.
$n\log n$
P10107
考虑链怎么做, 那么类比 CF1511G Chips on a Board 倍增的处理异或, 设 $f_{i, j}$ 表示询问 $(i, 2^j-1)$(恰好是考虑低 $j$ 位的答案, 因为低 $j$ 位和高为是独立的), 然后倍增跳就行了.
对树上的考虑对每层做前缀和. 即维护 $f_{i, j}$ 表示点 $i$ 及其同深度且bfs序小于自己的点查询距离为 $2^j-1$ 的答案之和, 此外为了合并需要维护 $g_{i, j}$ 表示点 $i$ 及其同深度且bfs序小于自己的点的子树中二进制第 $j$ 位 $1$ 的数量, 就行了.
而还有一个很厉害的做法是考虑直接把链上做法套个长剖, 把询问挂到点上自底向上在合并的同时统计答案, 这个做法不需要差分性感觉很强大.
复杂度都是单 $\log n$(倍增跳).
CF1876E Ball-Stackable
结论: 存在一个点使得其作为根时, 所有未定向的边都朝外. (其实都朝外这件事较符合直觉)
对已经确定的定向, 考虑对每个点定义高度 $h$, 满足若 $u\to v$, 则 $h_v=h_u+1$, 则发现同色边一定是一个连通块边缘上指向连通块内部的边, 是极大的除边界外 $h_u>$ 某值的连通块. 此时考虑若根在连通块外则恰有一条边是外向, 否则所有边都内向. 于是当根位于 $h$ 最小处时每个连通块对应一条外向边, 就证明出来了.
复杂度线性.
P10305 [THUWC 2020] 序排泡冒
$n$ 个点树, $q$ 次询问对链上点权序列 $a_1\ldots a_m$, 有多少个长 $m$ 的序列进行 $k$ 轮冒泡排序之后得到 $a$.
$n, q\le 5\times 10^5$
二合一题, 先考虑给定 $m$ 的情况怎么算, 则有经典结论
[trick] 一轮冒泡排序, 排序前前缀 $[1, i]$ 和排序后 $[1, i-1]$ 的数集只差一个最大值, 则 $k$ 轮后 $[1, i+k]$ 和 $[1, i]$ 差前 $k$ 大.
于是考虑比较 $a’{[1, i]}, a{[1, i+k]}$ 和 $a’{[1, i+1]}, a{[1, i+k+1]}$, 考虑 $a’{i+1}$, 若其是前缀最大值则可能原序列 $p$ 任意空位($[1, i+k+1]$ 且不是 $a’{[1, i]}$), 否则恰是 $a_{i+k+1}$
转化之后就是求前缀最大值数量, 因为没有修改所以不用楼房重建+lct, 一个2log做法是离线点分治+可撤销栈, 一个1log做法是直接在原树上搞, 维护 $g_u$ 表示 $u$ 祖先上第一个比它大的值, 则到lca之前的部分显然直接倍增, 后面的部分注意到前缀最大值相当于要求 $g_u$ 比lca浅, 并且要求值比 $u$ 左边那边更大, 于是dfs维护线段树就能做了. 复杂度单 $\log n$
Day2
模拟赛
A.
把每条边拆成两条边, 先强制选其中大的一条, 则此时大的那条边不影响连通性, 于是钦定其一定选, 若不连通增加边权即可, 从小到大扫边权模拟Kru, 状态设 $f_{i, j, S}$ 表示扫描权值到 $i$, 选了 $j$ 条 $a_i$ 的边, 且并查集状态为 $S$, 复杂度 $m^2\mathrm{Bell}(9)$
B.
考虑如果所有指针都指向父亲那么就是一个欧拉环游序, 循环节长 $O(n)$, 问题出在一开始指针不指向父亲到全部指向父亲的过程会经历 $n^2$ 步. 考虑把每个点的儿子分成两类, 在父亲前的(向左画)/在父亲后的(向右画), 则发现每次会走所有向左的边遍历树, 并把走过的点向右连的儿子也变成向左的, 于是把点按祖先路径上向右走的边的数量从小到大排序, 相当于不断在欧拉序上插入一个点(但始终是整棵树欧拉序的子序列, 所以线段树), 复杂度 $(n+q)\log n$
然后这题可以不要线段树, 用并查集支持找下一个还没有被加入到欧拉序上的点可做到 $n\alpha(n)+q\log q$
C.
首先连通性显然是拆成若干个段且 $[l, r]$ 的值域恰好是 $[l, r]$.
左/右是对称的, 只考虑左边.
把点 $(x, p_x)$ 画到平面上, 两步能当前点能到的范围内最左的点和最小的点决定, 推得每次都是由上步范围内最左的和值最小的得到, 需要 $k$ 步以上的点是一个2side矩形. 于是可以把一个范围记为 $(a, b)$ 表示某个点到达最左的点是 $a$, 最小的点是 $b$ 的情况下不能到的范围, 也即 $i\le a\And p_i\le p_b$ 的范围.
考虑每个点都会这样扩展出一串点对, 拆贡献为每个点对贡献为所对应区域内点数, 建树, 如果树大小可接受就是二维数点 $n\sqrt n$ 矩形查询 $n$ 次单点修改就赢了.
考虑分析树的大小, 对于点 $(x, p_x)$, 设与它构成逆序对的点序列为 $(a_k, p_{a_k})$, 设前 $B$ 个点是好的, 则一共有 $nB$ 个好点. 进行跳跃(找儿子)的过程中, 若当前位于一个与当前点为逆序对, 且非好点, 则至少会让范围的一条边长缩小 $B$(因为下次至少可以跳到 $(a_1, p_{a_1})$ 这个点), 于是对一个点, 其跳的坏点个数是 $\dfrac{n}{B}$, 总个数 $\dfrac{n^2}{B}$, 平衡得 $n\sqrt n$.
总复杂度 $n\sqrt n$
建树的时候直接哈希常数比较大, 更好的方法考虑从大到小扫描 $x$, 则容易发现越小的 $x$ 的父亲的 $y$ 越小, 于是给每个 $x$ 开一个有序 vector 维护所有的 $y$, 则插入父亲的时候只要判定是否和最后一个元素相同即可.
构造
CF1762G Unequal Adjacent Elements
注意到相当于要把序列划分成两个子序列, 间隔放置保证没有相邻相同元素.
容易猜到如果有一个数次数超过 $\lceil \dfrac{n}{2} \rceil$ 就无解.
如果存在绝对众数, 则显然把它们划分成一个子序列, 剩下的放到另一个子序列, 就是对的.
于是考虑把原序列划分成若干个有绝对众数的区间, 于是从前往后, 钦定当前 $a_1$ 为绝对绝对众数(总长奇数情况下)往后找极长区间, 现在问题是划到了最后可能剩下一段, 这段单独看是无解的,
此时把最后一段中的绝对众数拿出来和上一段合并.
todo
P9924 [POI 2023/2024 R1] Satelity
先考虑没有互不相同的限制, 则先A公司都填A, B公司都填B, 第 $i$ 个A公司的让第 $i$ 位为 $C$, 让所有与它相连的B对应位为C, 于是加上互不相同就再加一段在B处二进制编码, 现在用了 $n+\log_2 n$
考虑A连边相同的可以用一位去连边, 然后再在等价类中编码. 于是现在设A, B小的一边有 $x$ 个等价类, 最大的等价类大小分别为 $a, b$, 需要用是 $M=x+\log_2 a+\log_2 b$, $a, b\le n-x+1$, $M\le x+2\log_2(n-x+1)$, 发现当且仅当 $n-x+1=3, 5$ 时要用 $M=n+2$ 次.
但这里默认A公司, B公司之间都有交, 发现当有编码部分/等价类大于3的时候都是可以的, 于是特殊处理 $n=2$ 即可.
于是仍然要处理 $n+2$ 的问题, 注意这里不仅是要 $n-x+1=3$, 因为我们刚才用了 $a, b\le n-x+1$ 这个放缩, 所以只有两边都是最大等价类是 $3$(或都是 $5$), 剩下的都是 $1$ 的情况才会错, 考虑此时我们用2位编码 $3$ 个不同的卫星是很浪费的, 于是对于 $3$ 的情况把编码位拿出来构造, 此时两个编码类分别赋值(ACC和CCA), 可重的去连边, 发现就行了. 对于 $5$ 的情况类似构造CCAAC, CAACC, AACCC)(横过来读只要抄 $1\ldots 7$ 的二进制表示). 基本就是避免编码位浪费.
gym104821H
容易发现我们容易的铺 $2\times 4$ 的矩形, 所以直接解决了 $n=4k$ 的情况.
对于 $n=2k$ 的情况, 容易发现先铺完剩一行, 最后一行铺剩一个 $2\times 2$, 用经典套路黑白染色数格子得到不可能铺满所以这就是最优情况.
对 $n=4k+3$ 的情况, 观察样例得到 $3\times 3$ 可以做到只缺一个, 于是可以规约到 $4k+1$.
对 $4k+1$, 如果仿照上面的有一个 $5\times 5$ 缺 $1$ 的就赢了, 发现不行, 但tyy说搜 $9\times 9$ 缺 $1$ 的就有了. 于是做完了, 需要打表 $n=5, 13, 1$.
CF1646F
不容易想到考虑一个中间状态: 每个人都有 $1\ldots n$. 则此状态到最终状态只要考虑把每个人的作为行, 让每列是一个排列循环位移若干位, 则发现需要用 $\dfrac{n(n-1)}{2}$
而考虑如何让其他状态到 $\dfrac{n(n-1)}{2}$, 则编一个策略, 每个人优先给相同的, 否则给上一个人给过来的.
证明考虑势能分析: 仅考虑颜色 $c$, 设第 $i$ 个人有 $a_i$ 个该颜色的牌, 循环移位使 $a_n$ 为最小值, 设势能为 $\sum_i ia_i$, 则最后显然是 $\sum_i i$, 而只要保证 $a_n$ 作为最小值不给 $a_1$, 就使得每次操作会让势能减小 $1$, 总次数 $\sum_i i-\sum_i ia_i\le \dfrac{n(n-1)}{2}$
于是就做完了.
[trick] 考虑中间状态.
gym104891K
注意到表示 $n$ 个点需要用 $16n$ 个bit, 而你询问得到恰好 $16n$ bit, 所以你必须要做到完全利用信息. 即构造每条路径恰好长面积的一半, 任意 $k$ 条路径交是面积的 $\dfrac{1}{2^k}$ 这样的.
考虑分治, 则重点是考虑用一个分形的线去铺(希尔伯特曲线), 使得下层可以沿着分形的线去铺, 构造略.
Day3
模拟赛
A.
从小到大扫值域插入, 记录当前 $k$ 个集合的大小构成的集合即可, 状态数是带限制的划分数. 钦定上一个数放的集合大小以避免相同的数放到同一集合. 复杂度 $nkS$, $S$ 为一个划分数.
B.
考虑序列上扫描线扫右端点, 维护平面上每个点最右边能覆盖它矩形的编号, 把这些东西放在树状数组上就可以查询答案, 现在维护这个只要考虑把平面拆成若干个矩形的不交并, 然后因为数据随机所以任意时刻矩形个数在 $1000$ 左右, 直接就过了.
C.
注意到短边边长最大 $17$, 考虑轮廓线dp, 记录当前格子位置和轮廓线上是否有从上到下延伸的位置, 状态是 $nm2^n$, 转移 $O(m)$.
对带修改的时候考虑正/反各做一次dp在修改位置合并. 合并要保证这行对应位置相等, 用一个And卷积.
组合数学
ABC313Ex Group Photo
考虑如果 $a$ 确定, 显然把 $b$ 从小到大排序往里放
注意到一个位置只和相邻两个位置中最小值相关, 于是从小到大插入 $a$, 就能从小到大的确定所有间隔. 于是设状态 $f_{i, j, 0/1/2}$ 表示已经插入前 $i$ 小的 $a$, 序列两个端点是否插入, 已经形成 $j$ 个连续段. 复杂度 $n^2$
ARC171 E
容易发现一定是偶数步.
很难发现操作序列唯一对应棋子放置方案.
那么只要数操作序列, 考虑棋子经过的行上一定是若干相邻点匹配, 列上同理, 而再把行和列上的 若干对匹配 匹配起来就能得到一组棋子方案. 于是行和列实际上是独立的, 方案数相乘即可.
那么现在考虑行, 这个点原来在 $A$, $A$ 可能和 $A+1$ 或 $A-1$ 匹配, 考虑若和 $A+1$ 匹配, 枚举其左边有 $i$ 哥匹配, 右边有 $\dfrac{m}{2}-i-1$ 个匹配, 选出这些是简单组合数, 然后再乘上它们的顺序 $(m-2)! i$($A$ 一定在头上, 最后一步必须从左边跳过来).
[Gym104081D] Devil May Cry
相当于 $S_1\ldots S_m$ 构成 $1\ldots n$ 的划分, 限制 $\vert S_i\vert\le lim_i$ 且 $S_i\subseteq T_i$
于是优化自己卷积, 考虑如何对每个 $i$ 快速计算其某个位置的值(因为实际上是把 $T_i$ 所有满足大小限制的子集做FWT再相加的值).
即
回顾
$$
FWT(F)_i=\sum_j (-1)^{\vert i\And j\vert}f_j
$$
$$
FWT(F_k(x))i = \sum{\vert j\vert\le lim_k, j\subseteq T_k} (-1)^{\vert i\And j\vert}x^j=x^{\le lim_k}^{T_k-\vert i\And T_k\vert}(1-x)^{\vert i\And T-k\vert}
$$
然后求这些东西复杂度是 $nm2^n$, 瓶颈在于把上面的 $m$ 个 $2^n$ 集合幂级数卷起来, 容易想到先 $\ln$ 再 $\exp$, 因为上面每个东西形式都是 $[x^{1\ldots C}] (1-x)^A(1+x)^B$, 所以本质不同只有 $n^3$, 都 $\ln$ 掉复杂度 $n^5$.
最后复杂度就是多项式相加的 $nm2^n$
QOJ 8180 Bridge Elimination
首先众所周知点权之和乘积等于每个边双内选一个点乘起来再求和, 注意到可以先对确定的图乱填点, 容易发现是对称的, 也就是说点权可以最后乘上去, 剩下的部分就是对每个 $k$ 计算, 有 $k$ 个边双的图的边双大小乘积之和, 这个东西只要先能算 $n$ 点大小的边双, 再把这个卷起来就行了.
而对于边双我们有厉害的东西, 设无向连通图的GF是 $G$, 边双的GF是 $F$, 考虑 $1$ 所在边双, 则其向外连的都是割边, 相当于每个点上可以挂若干个无向连通图, 即 $G(x)=F(x\exp G(x))$, 其中 $G$ 已知, $F$ 未知.
记 $H=xe^G$, 有 $G(x)=F(H(x))$, , 代入 $H^{-1}(x)$ 有 $F(x)=G(H^{-1}(x))=$, 于是
$$
[x^n]F(x)=[x^{n-1}]\dfrac{1}{n}G’(x)\dfrac{x^n}{H^n(x)}
$$
暴力 $n^2$, 用多项式快速幂是单 $\log n$.
所以这个题是不是可以做到俩log, 我们考虑第一部分背包实际上是求
$$
p_n=[x^n]\prod_i (1+a_ix)
$$
显然分治FFT. 然后我们单 $\log n$ 求了 $F$, 现在只要求
$$
\sum_k p_k x^n^k
$$
转置是
$$
\sum_k c_kx^k^n
$$
单 $\log n$.
Qoj8171
考虑设 $i$ 次结束的概率是 $p_i$.
显然你没有什么好策略, 某时刻的情况是前 $i-1$ 位已知, 第 $i$ 位排除了一部分, $i+1$ 位往后完全不知道. 考虑第 $i$ 位此时会被问多少次, 因为完全未知可以认为我们依次尝试, 则发现在第 $i$ 位问 $0\ldots n-i$ 次的概率都是相同的 $\dfrac{1}{n-i+1}$.
于是可以直接写PGF, $P(x)=\sum_i p_ix^i$, 则 $P(x)=\prod_{i=1}^n \dfrac{1}{n-i+1}\dfrac{1-x^{n-i+1}}{1-x}=\prod_{i=1}^n \dfrac{1}{i}\dfrac{1-x^i}{1-x}$.
而我们要求的是 $[x^{m-1}]\dfrac{1}{1-x}P(x)=[x^{m-1}]\dfrac{1}{(1-x)^{n+1}}\prod_i (1-x^i)$, 后面这个东西是五边形数, 就做完了.
Qoj8217
容易发现等价于在 $(n+1)\times (n+1)$ 的矩形内填 $2\times 3$ 的矩形.
然后发现 $n\times n$ 到 $(n+6)\times (n+6)$ 是容易的.
于是去手动构造 $n=2\ldots 7$
Qoj8174 Set Construction
考虑对 $n, m$ 归纳减小规模, 并保持 $m$ 大约小于 $\dfrac{n(n-1)}{2}$
若 $m$ 为偶数, 直接把 $n/2, m/2$ 的答案弄过来, 令 $x$ 变成 $n-1, m/2$ 继承过来(最后一位添 $0/1$)
若 $m$ 为奇数, 变成 $n-1, m-1$(把所有数后面填 $1$, 最后加入一个 $0$)
Qoj7637 Exactly Three Neighbors
发现当使用 $n=1$ 时(用长条填充), 发现容易得到所有 $\le \dfrac{2}{3}$ 的比例.
剩下的写一个精细实现的搜索(? ? ! ! )
试着证明最大值是 $\dfrac{4}{5}$, 把边分为黑黑之间, 黑白之间和白白之间, 而前两类是固定的, 发现 $\dfrac{4}{5}$ 搜出来的解没有任何白白边.
Day4
模拟赛
A
对每个颜色考虑, 则建虚树, 发现一个当前颜色对当前询问贡献 $1$ 当且仅当询问的链和虚树有交, 于是虚树的点加 $1$ 边减 $1$ 贡献就是对的了.
需要动态维护 $n$ 个虚树, 写起来很爆炸.
需要处理链加链求和复杂度是 $n\log^2 n$, 显然可以麻烦的用全局平衡二叉树搞到单 $\log n$.
靠靠靠, 不用维护虚树, 你是对所有点加 $1$, 所有边减 $1$, 这不是我们 异象石 dfs序加一圈就做完了吗///fn
然后还有些其他做法, 再把路径有交拆成 虚树根在路径上 或 路径lca在虚树边上, 分别做.
B
你看这个 $16$, 基本上就是让你选个方向开始状压dp, 要控制轮廓线很小才能压下, 于是直接极角排序轮廓线dp可以做到 $N2^{m+1}$, $N$ 为点数大概是 $\pi nm$.
另一个做法是沿着 $y=-x$ 斜着dp.
C
看成是选 $k$ 组匹配, 选每个点有一个代价, 同组匹配之间付出差的绝对值的贡献, 于是有费用流做法: 建图 $i \stackrel{\inf, 1}{\longleftrightarrow} i+1, S \stackrel{1, a_i}{\longrightarrow} i, i \stackrel{1, b_i}{\longrightarrow} i+1
$ 即可.
然后就模拟费用流手动跑即可.
让我们看看这个可以做到什么, 考虑维护中间每个边被正向经过的次数 $c_i$(反向为负, 显然不会同时存在两个方向的反向边), 只需要考虑向右走的, 此时一个区间的权值是 $b_l+d_r+\sum_i [c_i\ge 0]w_i$, 要查询全局值最小的区间, 并支持区间加减 $1$, ban 掉单点.
然后这个看起来可以规约区间加减 $1$ 区间大于 $0$ 数个数, 考虑控制每个点附加的那个权值(即题目中 $b, d$ 的值)就可以控制区间位置, 然后问完一次之后反向问一次可以抹平修改, 而因为每个端点只会用一次, 所以控制第 $k$ 次修改的 附加权值是 $-k\cdot \inf$ 即可, 这个东西不能 $\mathrm{poly(\log n)}$, 直接考虑根号算法, 又因为区间加区间大于 $0$ 的个数就已经 $n\sqrt n$ 困难(叠! ), 考虑 $n\sqrt n\log n$.
此时这个东西很简单, 显然只要考虑一个方向的答案(这里考虑从左到右), 序列以 $B$ 大小分块分块, 每个块维护块内答案, 从某个位置开始到右端点的答案, 从左端点开始到某个位置结束的答案, 大于 $0$ 数个数, 这些信息显然只有 $B$ 种不同的值(每个数从负数变成正数), 然后这个处理一块可以 $B\log B$(线段树, 也是维护这 $4$ 个信息), 需要每个块记录一个指针指向当前对应答案, 区间加减 $1$ 只会移动 $O(1)$.
区间修改直接打标记并重构散块, 单点修改直接重构散块, 查询直接扫一遍求一下大于 $0$ 个数的前缀和, 然后就是最小化 $a_i-b_j$, 要求 $j<i$, 则直接记录 $b_j$ 前缀最大值即可.
分析复杂度, 查询是 $\dfrac{n}{B}$, 修改是 $B\log B+\dfrac{n}{B}$, 平衡得复杂度 $m\sqrt {n\log n}$.
线性代数
ABC276Ex
考虑某些子矩阵至少有一个 $0$, 其他的位置不能有 $0$, 于是不需要考虑 $0$ 的部分, 只要填所有非 $0$ 的部分剩下的全 $0$.
容易想到原根和前缀和, 于是现在有 $4q$ 个变量和 $q$ 个方程组.
然后注意到原根只关心奇偶性, 可以bitset优化高消, 做到 $q^3/w$ 过了.
矩阵快速幂
记个结论
若 $P(x)$ 是矩阵 $M$ 的特征多项式, $P_1(x)$ 是最小的零化多项式, 有结论
若 $P(x)=\prod_i (1-\lambda_i)^{a_i}$ 则 $P_1(x)=\prod_i (1-\lambda_i)^{b_i}, b_i\in [1, a_i]\cap Z$.
于是要求 $M^k$ 你就先把 $x^k$ 多项式取模就行了. 复杂度就是 $n^4$
QOJ 7612 Matrix Inverse
容易想到NOI2013 那个矩阵乘向量题, 考虑随一个向量一次乘 $AC$, 作为行一次作为列一次可以得到包含错的 $12$ 个行和 $12$ 个列, 得到 $144$ 个可能错的位置.
于是每一行单独拉出来列方程, 判它是不是单位矩阵就行了. 解方程复杂度是 $12^3n$, 列方程是 $12n^2$.
$n$ 阶范德蒙德矩阵行列式
是 $\prod_{1\le j<i\le n}(x_i-x_j)$
$n$ 阶循环矩阵行列式
设 $f(x)=\sum_{i=0}^n a_ix^i$, 则行列式是 $\prod_i f(w_n^i)$, $w$ 是单位根.
CF917D
令重合的边权是 $x$, 没重合的是 $1$, 于是用点值跑矩阵树可以到 $n^4$.
但上面做法可以对任意图做, 对于树可以做的更快, 考虑直接容斥, 则钦定 $k$ 条边相同, 然后Caylay+ $n^2$.
gym102978A
对分割线用LGV, 然后需要把起点终点平移以允许重合.
因为钦定了一个点的点值, 所以会要求某条分隔线在这个点的左/右, 所以让所有经过这个点左边的有权值 $x$ 右边的有权值 $1$ 就做完了.
然后这个题和上个题的行列式都可以特征多项式优化, 因为刚才我们特征多项式 $n^3$ 可以求, 所以所有 $\vert Ix+A\vert$ 都可以优化.
Day5
模拟赛
A.
容易发现你改一个点整棵树都要变, 但这个问题看起来很像那种dp每次改一条链的东西, 然后注意到一个子树内答案是关于子树根父亲的二次函数, 设点 $u$ 的函数是 $f_u(x)$, 容易发现 $f_u(x)=\min_t f_{lson}(t)+f_{rson}(t)+(t-x)^2$, 则 $t$ 可以直接求, 然后还是二次函数, 然后做完了, 复杂度 $n2^n$.
B.
观察给了个 $\sum k^2$ 的条件.
容易发现显然能直接走的肯定直接走, 考虑 $u$ 不能直接走的点 $v$, 若路径是 $u\to x\to t_1\ldots t_k\to v$, 则其中 $x$ 是 $u$ 一步走到的, 而 $t_1\ldots t_k$ 都是 $u$ 不能走到的, 于是问题变成一个 $k$ 大小子图, 每个点有一个初值($u\to x\to t_1)$ 长度), 要在里面求最短路, 这部分是 $\sum k^2$.
然后只要对所有 $u\to v$ 边不存在的点对 $(u, v)$ 求 $u\to x\to v$ 的最小值, 然后这种不存在边的经典做法是拆成 $k$ 个区间, 于是开一个线段树存每个点出边值, 枚举 $v$ 统一算 $u$, 则 $v$ ban掉若干个点, $u$ 去查拆出来的区间最小值即可. 这里要对同一个 $v$ 一起处理是因为 $\sum k_{in} k_{out}$ 是可以很大的, 统一处理就成 $\sum_k$ 了.
哦, 也可以不线段树, 开一个堆塞所有点, 枚举 $v$ 删掉所有不连向 $v$ 的点, 再逐个枚举 $u$ 删点并撤销删点.
最后复杂度 $(\sum k^2)\log n$
C.
/bx/bx/bx alan_zhao
考虑你选出来一定是个凸包, 于是对凸包dp就行了, 先枚举一个点钦定其是凸包上纵坐标最小的点, 对剩下的点按极角序dp, 设 $f_i$ 表示dp到 $i$ 的时候的答案, 枚举下一个点转移, 此时要算一个三角形内有多少 牛肉 . 想到叉积算面积那个方法, 于是记录前缀和容斥即可.
复杂度 $n^3$
/bx/bx/bx cxm
一个经典trick是把所有边拿出来跑, 和zyz的做法本质相同.
dp
gym103447A
回文自动机的结构很差! 只有一半!
容易想到从两边往中间走, 左边匹配到 $l$, 右边匹配到 $r$, 左边/右边还剩 $i$ 个没匹配的方案数是 $f_{l, r, i}$, 状态数是 $n\sum len$, 转移 $O(1)$.
USACO 24Feb Platinum B
考虑每两个被固定位置之间的排列是确定的, 一定是从左到右选, 此时答案就是 $\sum a_i+max-min$, 只要管极差的部分. 也就是划分成 $k+1$ 个集合, 每个集合贡献其并上两个额外元素后的极差.
发现一个性质, 因为是极差, 所以每两个集合选出的值域要么包含, 要么不交, 于是可以把包含关系建树, 则 $f_{l, r, S}$ 表示 $[l, r]$ 这个区间, 已经填好了 $S$ 集合的集合, 则每次可以
- 向左向右扩展一个, 放到一个新背包(这里先不转移)
- 把当前区间内用上面那个转移转移的的放到一个新背包(可以根据区间长度判断)
- 拆成两个子区间
拆成两个子区间的时候可以钦定两个子区间都是刚刚用第二个转移转移过(没有空余元素), 就不需要枚举划分点, 复杂度是 $m^23^k$
CF301E
良好序列可以对应括号序列, 考虑折线, 然后cxm和zyz说做过一个题是钦定折线每层有多少个数, 数方案数的题. 做法是经典的从下往上在值域上扫折线, 此时折线上有若干个洞需要填入更大的数.
而优秀数列实际上是在让你数多重集, 于是把刚才那个东西像dp套dp一样放在里面, 即 $f_{i, j, k, l}$ 表示从小到大插入到 $i$ 这个数, 已经用了 $j$ 个数, 有 $k$ 个洞, 有 $l$ 种方案, 则插入的时候容易转移出这个问题.
为什么这个dp套dp不像一般的dp套dp一样只有一维不是指数呢? 感觉是因为外层dp和内层dp结构高度一致.
Ternary String Counting
暴力是记录 $f_{i, j, k}$ 表示前 $i$ 个位置, 最近的与 $i$ 不同的颜色是 $j$, 第二近的是 $k$.
$$
f_{i, j, k}\to f_{i+1, j, k}, f_{i+1, i, k}, f_{i+1, i, j}
$$
然后你会限制 $j$, $k$, 发现每次只会让增加一行是非 $0$ 值, 也就是说暴力清空非 $0$ 位置就是对的. 为了实现这个可以开 $n$ 个deque.
Gym 103470I
你看这个路径很菜, 虽然弯来弯去只有不同的 $2H$ 种状态, 显然设 $f_{i, 0/1}$ 表示从 $i$ 出发, 当前方向向上/向下的最大贡献, 做上面的路径转化之后就直接做了.
复杂度排序外线性.
AGC028E
So strong
见字典序想贪心, 然后现在固定 $S$ 的一个前缀, 即固定了 $A$ 和 $B$ 各一段前缀最大值, 考虑判定.
考虑 $p$ 序列中的前缀最大值, 它们一定在 $A$ 或 $B$ 中是前缀最大值, 而若 $p_i$ 非前缀最大值但是在 $A/B$ 中是前缀最大值, 则说明 $i$ 前面的前缀最大值在 $B/A$ 中, 于是对非 $p$ 前缀最大值的两个元素 $i, j$, 若其对应序列中前面最近的前缀最大值是 $m_i, m_j$, 且因为 $p_{m_i}>p_i, p_{m_j}>p_j$, 所以 $m_i$ 和 $i$ 在不同的序列, $j$ 同理, 所以交换 $i$ 和 $j$ 所在的序列, 一定能同时删去这两个元素, 于是可以让还没填的部分中 $A$ 或 $B$ 中的一个中所有元素都是 $p$ 的前缀最大值.
于是只考虑B中存在非前缀最大值的情况, 从前往后走, 设 $A$, $B$ 前面已经钦定的部分分别有 $c_a, c_b$ 个前缀最大值, $A$ 后面选了 $h_a$ 个 $p$ 中前缀最大值, $B$ 后面的前缀最大值中有 $h_b$ 个 $p$ 中前缀最大值和 $n_b$ 个非 $p$ 中前缀最大值, $p$ 后面一共有 $h_p$ 个前缀最大值. 有 $c_a+h_a=c_b+n_b+h_b$, $h_a+h_b=h_p$, 于是 $c_a-c_b+h_p=2h_b+n_b$ 为定值. 只要存在一个这样的序列 $B$ 算出来是对的就行.
而且发现, 你总可以把一个 $B$ 中前缀最大值元素放到 $A$ 以把它减小 $2$, 所以其取值在奇数/偶数分别是一个前缀. 于是要求分别情况的最大值, 然后这个可以从后往前dp. 然后这个是简单dp+线段树优化. (这个线段树的算出来的值对A和B是一样的只要写一遍)
复杂度 $n\log n$.
Day6
模拟赛
A
靠, 智障完了.
容易发现任意时刻你选了的位置一定是一个前缀扣掉至多两个点, 于是智障dp是 $f_{i, j, k}$ 记录三个点, 则每次钦定进行一段连续的 $3$ 操作再进行一次已操作, 则任意时刻最多扣掉一个点, 只要记录 $f_{i, j}$ 表示前 $i$ 个, 扣掉 $j$. 转移显然.
然后唐处在于这个dp只要记录能否达到这个状态而不用记值, 因为你每个状态对应的值是确定的, 于是bitset优化到 $\dfrac{n^3}{w}$ 过了.
B
怎么大家都这么厉害
mikefeng的做法: 考虑合并值域上连续的连通块, 设 $f_{l, r, i, j}$ 表示 $[l, r]$ 这个值域区间组成的连通块, $i, j$ 为其中最小值, 最大值位置, 则若合并 $f_{l_1, r_1, i_1, j_1}$ 和 $f_{l_2, r_2, i_2, j_2}$($l_2=r_1+1$)时, 讨论 $j_1, i_2$ 是否相邻, 若不相邻只能转移到 $i_1, j_2$, 否则若相邻且其中一个是单点则最大/最小值位置可能变化.
然后连通块合并显然是 $O(n)$ 的, $i, j$ 都只用 $O(1)$ 种. 复杂度线性吧.
zyz的做法:
考虑一个极大的置换环, 设其中的最小值是 $u$, $u$ 连着的值是 $x$, 则作为置换环的一部分 $u$ 要想换一定是当时 $x$ 的位置是 $u+1$, 容易发现形态一定是 $u+1\ldots x-1$ 都连在 $x$ 上, 此时 $1\ldots x-2$ 都不可能再换, 但 $x-1$ 可能是由子树内换上来的, 发现是个子问题, 于是这么找下去. 这样做可以获得所有合法的置换环, 于是在值域上dp一遍就可以得到用置换环组合出整个序列的方案数.
juefan的做法:
考虑一个很典的dp, $f_{u, v, w}$ 表示 $u$ 子树换出去 $v$, 换进来 $w$. 然后 $w$ 必然是 $v-1$ 或 $v+1$, 优化掉一维, 再考虑 $f_{u, v, 0/1}$ 中, $v$ 一定距离 $u$ 距离不超过 $2$, 于是要么把 $u$ 换出去, 要么传到下面去要求儿子给出来. 复杂度也是线性.
C
垃圾分讨
图论
CF718E
预处理颜色到点的最短路 $dis_{u, c}$ 和颜色到颜色的最短路 $w_{c_1, c_2}$, , 则 $x\to y$ 的最短路是 $\min{\vert x-y\vert, \min_c dis_{x, c}+dis_{c, y}+1}$. 枚举 $x$, 考虑右边的东西最大值很小($2S$), 枚举 $x$ 前 $2S$ 个点暴力计算, 对于选择 $dis_{x, c}+dis_{c, y}+1$ 的点对, 前面只有 $S2^S$ 种点(对应点的颜色, 以及这个点到 $x$ 对应颜色), 枚举点的种类统计答案即可.
CF1062F
拓扑排序时, 任意时刻队列中的点一定无法相互到达. 在正图反图分别跑一遍是充分的, 于是在删除每个点时更新每个点和它互相不可达的点的个数.
需要证明正图反图分别跑是充分的, 考虑 $x, y, z$, $x, z$ 相互不可达, 那么正图遍历时 $x, z$ 不同时在队列里一定是因为存在 $z$ 可到达的点 $y$, $x, y$ 是同一层的而 $z$ 在 $x$ 之前的层, 而 $x, y$ 同时在队列, 那么发现反图就不会有这样的 $y$, 于是 $x, z$ 在同一层.
CF1250K
考虑分配普通投影仪使得之后任意时刻高清投影仪使用数量少于 $y$, 若一个时刻要用 $a$ 个投影仪, 则普通投影仪至少要用 $a-y$ 个, 至多能用 $x$ 个, 时刻 $i$ 用 $i\stackrel{[a-y, x]}{\longrightarrow} i+1$ 表示, 对一个研讨会连边 $r\stackrel{[1, 1]} l$ 就做完了.
loj养猫
对第 $i$ 个时刻设变量 $x_i$, $x_i=1$ 为睡觉, $x_i=0$ 为吃, 则限制是 $\forall i, L\le \sum_j x_j\le R$, 变成 $L+y_i=\sum_{j=i}^{i+k} x_j=R-z_i$, 然后相邻两个作差可以得到 $x_{i+k+1}-x_i=z_{i+1}-z_i=y_{i+1}-y_i$, 最后还有两个 $\sum_{j=1}^{k}x_i\in [L, R]$ 的式子, 则都移动到一边, 每个变量出现一正一负两次, 于是转费用流, 每个等式对应一个点, 每个边对应一个变量即可.
WF17 小小水管工
猜测 $W$ 关于 $F$ 一定是凸的, 于是直接三分 $F$, 然后用上下界最大流限制 $F$ 跑一遍最大流, 再在剩下的部分跑 $W$ 的最大流即可.
但是实际上这东西很厉害, 说的是不考虑 $W$, $F$ 最大值是 $F_m$, 不考虑 $F$ 设 $W$ 的最大值是 $W_m$, $F+W$ 的最大值是 $V_m$, 则 $F_m \le F, W\le W_m, F+W\le V_m$ 是存在合法方案的充要条件, 证明考虑先流好 $F$, 在这个基础上跑 $W$ 一定能跑到 $V_m$, 我们有方法得到 $(F_m, V_m-F_m)$ 的方案, 有方法得到 $(V_m-W_m, W_m)$ 的方案, 则满足上面条件的 $F, W$ 都可以表示成这两组方案的每条边分别乘上 $a, (1-a)$ 对应加起来得到的方案, 就对了.
然后直接求最大值.
Gym101194J
典是把 L形 拆成左右选一个, 上下选一个.
网格黑白染色, 每个格子拆出点入点, 对黑点出点决定横管, 入点决定竖管, 白点用出点决定竖管, 入点决定横管, 每个点的入点连向相邻点的出点, 就做完了.
[trick] 黑白染色, 相邻匹配不是很典吗/fn
Day7
模拟赛
A
手玩小样例注意到 $k=2^{n-1}$.
考虑在 $n$ 的基础上获得 $n+1$ 的答案, 则把 $2^{n-1}$’个图每个复制一份获得 $2^n$ 个, 而 $n+1$ 这个点和其他点的连边方式有 $2^n$ 种, 只要保证由同一个方案复制得到的两个图对应的 $n+1$ 连边方案互补.
还有什么神奇方法, 打表发现存在一组解是所有完全二分图.
B
注意到每次用循环移位的把最小值移动到第一位复杂度是调和级数的 $\ln n$, 且期望在 $1$ 左右, 于是随机一个排列 $p$, 先把初始排列变到 $p$ 再变到正确的就期望对了.
另一种做法是固定所有 $p_i=i$ 的位置移动其他的, 期望也不到 $1$, 也用上面的做法.
正解是类似对值域分治, 但要把同一分治层内所有区间一起做, 则现在问题就是有 $2^k$ 个 $\dfrac{n}{2^k}$ 的区间, 每个区间内有一半 $0$ 和一半 $1$, 要把这些 $1$ 弄到后面, 此时只要每次选中每一段第一个数和其中所有的 $1$ 进行移动, 可以用 $\dfrac{n}{2^{k+1}}$ 次操作.
C
注意到进行下面的操作可以把两个环上的 $0$ 和 $1$ 交换(位置并非不变, 但所在环是对的). 就做完了.
$\texttt{xxx1xxx}, \texttt{yyy0yyy}\to\texttt{yyyxxx}, \texttt{yyy0xxx1}\to\texttt{0xxxxxx}, \texttt{yyyyyy1}$
杂题选讲
WF2021 E
考虑Bob和Alice的策略不是你能想到的, 应该是Alice和Bob约定Bob的每一种局面Bob应该猜几. 而发现每种颜色在局面是独立的, 所以得到答案是
$$
\sum_ \dfrac{1}{\binom{n}{k}}\min{\sum_i \binom{c_i}{a_i}, \sum_i \binom{c_i}{a_i-1}\prod_j\binom{c_j}{a_j}}
$$
CCPC FInal 2023 B Periodic Sequence
注意不到, 任意时刻字符串一定形如 $s_{1\ldots k} + s_{1\ldots a_1} + s_{1\ldots a_2} + \ldots + s_{1\ldots a_m}$, 其中 $s$ 为第一次的字符串(一定长 $n$, )$\forall i, a_i\le k$.
于是直接开始数数:
$$
[x^n]\dfrac{1}{1-x} \sum_{k=1}^n \dfrac{x^k}{1-\dfrac{1-x^{k+1}}{1-x}}=[x^n]\sum_k \dfrac{x^k}{1-2x+x^{k+1}}
$$
todo
CF1456E
考虑一个点没有上下界, 那么它应该和前面的一样. 将连续的这些点合并, 就只要管不同的位置, 则从高到低dp, 逐渐会有点没有上/下界限制, 于是设 $f_{k, l, r}$ 表示从高位开始dp到第 $k$ 位, 当前扩展到 $[l, r]$, $[l, r]$ 有限制, 从高位往低位转移就对了.
CF1270I Xor on Figures
这个题很像GDKOI 染色. (南外省选集训NOI模拟赛27 B)
考虑现在一个点 $(p, q)$ 操作一次是给所有 $(p+x_i, q+y_i)$ 翻转, 那么在所有 $p+x_i, q+y_i$ 再操作一次, 注意到此时所有 $(p_x+x_i+x_j, p_y+y_i+y_j)=(p_x+x_j+x_i, p_y+y_j+y_i)$ 都消了, 相当于进行 $(p_x+2x_i, p_y+2y_i)$ 的操作, 于是每次乘 $2$ 的操作, 则到 $p_x+2^kx_i, p_y+2^ky_i$ 的时候就只操作单点, 就构造出来了方案.
CF1276E Four Stones
考虑这么跳的时候, $3$ 块石头之间的间距的 $\gcd$ 应该不会变, 且考虑过程是可逆的, 只需要实现把间距变成 $\gcd$ 操作再变回去.
设三个间距分别为 $d_1, d_2, d_3$ 设 $d=d_1+d_12+d_3+d_4$, 若 $d_1\in [\dfrac{d}{4}, d-\dfrac{d}{4}]$ 则发现把第一个点关于第二个点对称至少可以让 $d\gets \dfrac{3d}{4}$, 只要做到这件事.
那么不满足条件要么是 $d_1, d_3$ 都很小 $d_2$ 很大, 要么是 $d_1, d_2$ 很小 $d_3$ 很大, 则只要倍增的缩小, 对于第一种把 $1$ 号点关于 $3, 4$ 号点各对称一次就能把一边变大另一边的 $2$ 倍, 第二种把 $1, 2, 3$ 不断用最远的点离最近的点对称就对了.
然后需要支持把这样的一个东西平移一个距离, 只要再支持把每个点之间距离各变大一倍, 然后倍增着跳就对了.
Day5
模拟赛
怎么又搬一遍一轮D1T1 fib.
B
看懂了0
C
这个东西很像endpos集合啊, 所以反过来建SAM考虑贡献, 发现同一等价类的直接贡献就做完了, 对于后缀树上不同的两个等价类 $a, b$, 其endpos分别为 $E_a, E_b$, $a$ 是 $b$ 的祖先, $E_a\mathrm{xor} E_b$ 的集合是 $E_a$ 的一个前缀, 且其设中最小的元素 $p$, 则 $(a, b)$ 贡献 $\max(0, len_b-p)$.
但直接做贡献点对是 $n^2$ 量级的, 考虑对每个等价类 $a$, $E_a$ 删去前若干元素后得到 $E_b$ 则连边 $a\to b$, 则构成一个以空集为根的内向树 $T$, 发现一个点对自己每个子树的贡献是相同的(因为 $p$ 是 $E_a$ 中 $mn_b=\min_{i\in E_b} i$ 的前驱, 之和 $p$ 有关), 于是只要想怎么在SAM找到每个点会连向谁.
考虑对于点 $u$, 连向 $u$ 的一定是一个到根链上的区间, 其中每个点 $v$ 满足不存在 $u$ 子树外的endpos $>mn_u$, 这个可以倍增/单调栈上二分得到最高的区间, 但问题是覆盖一个点的所有这些区间中 $mn$ 最小的才是它 $T$ 上的父亲, 于是用并查集支持修改即可.
比较震撼的是, 这种东西可以用SA做, 先做SA考虑对Height建笛卡尔树然后从小到大合并的时候考虑状态. 不过好像要写7k(比我上面那玩意还长).
然后实际上上面不需要显示建树 $T$, 直接在原后缀树上考虑就行, 而且新树上一条祖孙链在原树上对应一个区间, 可以大大降低码量.
复杂度都是单log.
D
官方题解:
考虑将 $nm$ 球标号为 $1$ 到 $nm$, 如果我们能把球按标号排序的话, 最后把答案调整到每根柱子同色就很简单了. 先考虑将第 $i$ 根柱子的球的集合变成 $[(i - 1) \cdot m + 1, i \cdot m]$. 考虑冒泡排序, 我们需要做的就是考虑相邻两根柱子, 将小的一半放到左边, 大的一半放在右边. 此时可以把小的看成白色, 大的看成黑色. 此时我们可以把两根空柱子挪到这两根旁边. 然后从上向下扫描这两根柱子, 把白色的扔左边, 黑色的扔右边. 会出现问题的情况是左边第一个是黑色, 右边第一个是白色. 此时需要交换两根柱子(交换两根柱子的情况可以自行思考一下, 在此不多做描述). 下面考虑将一根柱子排序, 由于有两根空柱子, 考虑基数排序, 每次将二进制为 $0$ 的放右边, 为 $1$ 的放左边即可. 需要注意的是移动空柱子时原来柱子上的球会 reverse, 在排序的时候需要考虑一下这种情况.
数据结构
SCOI2014 方伯伯的玉米田
显然一个dp. 然后数据结构优化一下做完了.
出处不明题
$n, m\le 10^5$
这种玩意肯定得离线把时间维加进去, 则相当于找一个时间递增的路径 $t_1\ldots t_k$, 于是考虑点分治, 若再时刻 $T$ 询问颜色 $c$, 就要求点 $c$ 到分治中心 $rt$ 的最早时间 $st_c$, 和从 $rt$ 开始, 值在 $[st_c, T]$ 的递增路径到达的点的数量.
对第一部分, 每个点记录 $f_{u, i}$ 表示从从第 $i$ 次让 $u$ 和父亲 $fa_u$ 交换情报开始 $u$ 最早能走到根的时间即可转移(去父亲那查一下后继).
对于第二部分, 扫描 $T$, 维护 $f_x$ 表示 $rt$ 最晚从 $f_x$ 开始能走到 $x$(从 $T$ 时刻出发逆着时间走的最短时间), 用第二种视角发现又容易转移了. 然后用BIT支持查 $f$ 大于某值的即可.
CF1408H Rainbow Triples
二分答案 $k$, 则 $0$ 一定是最左边 $k$ 个 $0$ 和最右边 $k$ 个 $0$ 匹配, 而且包含不如交叉, 则一定是从左到右依次匹配, 于是直接确定了 $k$ 个区间去和区间内的非 $0$ 点二分图匹配. 于是上Hall定理, 此时要求 区间并颜色数 减 区间数 的最小值, 考虑这些区间的结构, 显然你选的区间的左端点在所有区间的左端点集合的rank构成一个区间(就是选一段左端点 “连续” 的区间), 于是直接扫描线, 扫描线维护颜色数是广为人知的.
现在复杂度是 $n\log^2 n$, 发现你的二分什么也不做, 实际上选择从 $l$ 到第 $r$ 个区间左端点对应的区间的限制是若 $k\ge \max(i, j)$, 则有一个答案最大值限制, 于是去掉二分复杂度单log.
GYM102586A
qyc的分析收录在ds
P6256 [ICPC2019 WF] Directing Rainfall
容易找到一种拓扑序, 使得不存在后面的板子上的水落到前面上的, 这个直接set+扫描线.
然后就dp, $f_{i, j}$ 表示后 $i$ 个线段, 其中第 $i$ 个线段在第 $j$ 个区间下落的答案, 转移是区间加 $1$ 和做前/后缀min, 考虑这玩意有均摊: 对于一个区间求一次前缀min再求一次后缀min就一样了, 所以Segment Tree Beats, 每个区间记录当前是否是单调增/减, 然后对一个已经有序的区间操作时可以转化成一次区间赋值, 对无序的区间, 假设是取前缀min, 从左到右每次二分出下一个前缀min转化成区间赋值.
分析复杂度, 取势能是前缀min/max个数的最大值, 每次可以用 $\log n$ 的代价消去一个, 同时一次修改会最多令 $O(\log n)$ 个区间增加 $O(1)$ 个, 所以总复杂度是 $n\log^2 n$.