由于博主很菜，不保证回忆准确无误。

D1T1

题意：

你有一个长度为 $k(k\leq 20)$k(k≤20) 的序列，有 $n(n\leq 1e5)$n(n≤1e5) 次操作，每次操作会给你一个长度为 $k$k 的序列 $b$b 和一个位置 $p$p ，假设你当前手里序列是 $a$a，如果 $b_p > a_p$bp​>ap​ 就会将 $a$a 序列整个替换成 $b$b。

操作序列在初始时告诉你且不会修改。

现在有 $q(q\leq 1e5)$q(q≤1e5) 次询问，每次给出初始序列 $a$a ，问在执行了操作序列中的操作之后的最终序列长什么样子。

时限 $3s$3s

口胡：

签到题，由于替换是整个操作，我们处理出原序列被替换成了某个序列的答案，然后对于询问，找到第一次替换发生的位置即可。

预处理直接倒着来就行了。注意我们需要维护前缀最大值，要开一个单调栈。

D1T2

题意：

给你一个有向图 $G=\{V,E\},(|V| \leq 1e5,|E| \leq 1.5e5)$G={V,E},(∣V∣≤1e5,∣E∣≤1.5e5) ，每条边有经过次数的限制。

有$q(q\leq 3e5)$q(q≤3e5)次询问（但是我看ouuan说是$q\leq 1e5$q≤1e5？），每次给一个初始位置 $u$u 和步数限制 $s$s，按照如下规则进行游走：

1. 如果当前点没有可以走的出边或者已经达到步数限制，结束。
2. 否则选择所有出边中编号最小的，走过去。

游走是具有后效性的，即每条边被经过的次数在全局进行统计，而不会在每个询问后进行重置

时限 $8s$8s

口胡：

这道题算是救了我一命，幸好这道题调出来了，不然我可能就真的凉了。

把每个点的当前选择的出边拎出来，显然是一个基环树森林。

直接LCT维护基环树森林，对于询问大力分类讨论就行了。

一个小时能A的我请你嚯冰阔落

D1T3

题意：

现在网上找得到的题意都是已经转化过的，我来口胡一个隐约记得的未转化的题意。

给一棵大小为 $n(n\leq 3e5)$n(n≤3e5) 树，定义 $dis(u,v)$dis(u,v) 为两点树上路径需要经过的边数。

有 $q(q\leq 6e5)$q(q≤6e5)次询问，每次给一个区间 $[l,r]$[l,r]，问标号在 $[l,r]$[l,r] 的点集 $S$S 有多少个子集满足是 $X-连通$X−连通 的，（$X$X 是一个开始就给好了的变量）

定义两个点 $u,v$u,v 是$X-关联$X−关联 的，当且仅当以下条件成立：

1. 存在一个点的序列 $p$p，长度为 $t$t，使得 $p_1=u,p_t=v$p1​=u,pt​=v
2. 对于 $1\leq i < t$1≤i<t，$dis(p_i,p_{i+1})\leq X$dis(pi​,pi+1​)≤X
3. 对于 $1\leq i\leq t$1≤i≤t，$l\leq p_i \leq r$l≤pi​≤r

定义一个点集 $V\subseteq S$V⊆S 是$X-连通$X−连通 的，当且仅当以下条件成立：

1. 对于任意 $u,v\in V$u,v∈V，$u,v$u,v 是 $X-关联$X−关联 的。
2. 对于任意$u\in V,v\in S/V$u∈V,v∈S/V，$u,v$u,v 不是 $X-关联$X−关联 的。

时限 $6s$6s

题解：

容易发现就是要把距离不超过 $X$X 的点连边，然后求 $[l,r]$[l,r] 的导出子图连通块个数，转化题意用不了多少时间。

我现在也不会，放一个神仙发在UOJ群里的题解

D2T1

题意：

你有一个初始值 $s(|s|\leq 15)$s(∣s∣≤15)，和 $n(n\leq 15)$n(n≤15) 次变换操作，第$i$i次操作形如 $s=a_i |s|+b_i \cdot s+c_i$s=ai​∣s∣+bi​⋅s+ci​ 。

请你调整操作的顺序，最大化最终 $s$s 的值。

$|a|,|b|,|c|\leq 15$∣a∣,∣b∣,∣c∣≤15，时限$1s$1s。

口胡：

听说很多错误做法能过pp。。。

一个比较naive的想法是维护最大最小值，大于$0$0的最小值和小于0的最大值。

最大最小值就可以维护了，但是后面两个东西目前仍然有点尴尬。

注意到$s$s实际上变成了 $(a+b)s+c$(a+b)s+c 或者 $(b-a)s+c$(b−a)s+c，也就是 $ks+c$ks+c 的形式。

$k=0$k=0的情况直接判掉不管，否则 $|ks|$∣ks∣ 的值相对于 $s$s 总是不减的，后面一个 $c$c 最多导致绝对值变化$15$15。

维护 $-225$−225 到 $225$225 的可达性即可。

复杂度视实现从 $O(2^n\sum c)$O(2n∑c) 到 $O(2^nn\sum c)$O(2nn∑c) ，不过由于根本卡不满所以能过。

D2T2

题意：

给一张 $DAG$DAG 图 $G=\{V,E\}(|V|\leq 1e5,|E|\leq 1.5e5)$G={V,E}(∣V∣≤1e5,∣E∣≤1.5e5)，令 $T$T 为 $G$G 的 $DFS$DFS 树（优先 $DFS$DFS 编号小的节点）。$q$q 次询问 $(q\leq 1e5)$(q≤1e5) ，每次给两个点 $u,v$u,v，保证 $u$u 是 $v$v 的祖先，请你回答在删掉 $u,v$u,v 树上路径的所有边之后，有多少点无法从 $1$1 号点到达。

时限 $1s$1s

口胡

一个比较显然的想法是对于每个点 $u$u ，求出最高的一个祖先 $f_u$fu​，使得 $f_u$fu​ 能够不经过 $<u,f_u>$<u,fu​> 树上路径上的边到达$u$u。

先考虑在知道 $f_u$fu​ 之后怎么处理询问，对于点 $u$u ，在 $f_u$fu​ 处我们就可以将 $[in[u],out[u]]$[in[u],out[u]] 标记为可达。那么询问 $(a,b)$(a,b) 的时候我们需要的就是 $a$a 到根的合法区间的并在 $[in[b],out[b]]$[in[b],out[b]] 中有多少元素。

可持久化线段树即可。

回到开头，怎么求$f_u$fu​。

下来想了半天总算想明白了，类似半支配点的求法，按照DFS序倒着处理，对于$u$u，我们枚举除了父亲以外所有能够到$u$u的点，很容易注意到我们要求的就是这些点在反图中不经过$u$u的任何祖先边，能够到达的最高的$u$u的祖先，直接带权并查集维护一下就行了。（和求半支配点唯一的区别就是不能考虑父亲）

MD这才是D2签到题，我真TM是个铁憨憨

D2T3

给一棵树 $(n\leq 5e5)$(n≤5e5)，不修改，有 $q(q\leq 5e5)$q(q≤5e5) 次询问，每次给一条有向路径和一个数 $k$k ，询问把路径上的点的序列拿出来，求有多少个序列在经历了 $k$k 轮冒泡排序后得到该序列。

时限 $4s$4s

不会

翻到一篇题解，还没看：here。