最近不想写题。
1. P8456
简单题。
显然要容斥计算同色路径的个数。无向图路径问题，考虑把边双缩点，建立圆方树。不难想到对每个方点分类：全 D，全 d，有 D 有 d。并查集维护每个全 D，全 d 极大连通块的大小即可。
这样会算多。考虑 \(x-y,y-z\) 为 D，\(z-x\) 为 d 的三元环，这会形成异色方点，但是内部要减去一种 两种颜色分界点 为起终点的路径。
2. P8528
一眼支配对。
每次询问，我们显然只关心 \(l\leq a_i\leq r\) 的点。
正难则反，考虑二元组 \((x,y)\) 不满足 \(a_x\leq a_{\text{lca}(x,y)}\leq a_y\)。考虑一个 \(x-y\) 平面，描绘了所有的合法点对 \((L,R)\)。那么不满足条件的点对 \((a_x,a_y)\) 会对 \(L,R\) 分别是一段前缀和一段后缀，放在二维平面上就会覆盖一个矩形。
注意到这样一件事情，对于同样的 \(\text{lca}\)，对于 \(x\)，如果 \(a_z\leq a_y\leq a_x\)，那么我们只需要保留 \((a_y,a_x)\)，因为更小的会被支配。因此对于一个集合中的点，只需要找前驱和后继。
维护子树中所有 \(a_i\) 的集合，可以启发式合并，这样有用的点对数是 \(O(n)\) 对的。
问题转化为，矩形覆盖，查询子矩形未被覆盖的面积总和。可以转化为区间加，询问区间历史 \(=0\) 的个数和。\(=0\) 不好维护，转化成最小值个数，每次对历史和打标记只对最小值 \(=0\) 的打就行了。
3. P9992
考虑对 \(\text{dfs}\) 序以及深度以及 \(h_u=\max_{v\in \text{subtree}(u)} \text{dep}(v)\) 进行二维偏序。
平面上应该是 \((\text{dfn}(u),\text{dep}(u))\)，一个子树作出贡献时，需要用 \(h_u\) 来容斥掉不合法的。
4. AT_agc060_c
引理：从 \(U=\lbrace1,2,3,\cdots,x+y\rbrace\) 中随机选取大小为 \(x\) 的子集 \(S\)，则 \(\min(S)<\min(U\setminus S)\) 的概率为 \(\dfrac{x}{x+y}\)。
证明：考虑 \(1\) 所在 \(S\) 的概率。
这个引理在修改为相对大小时就是下面要用的。
没法算方案数，只能算概率。考虑自底往上跑 dp。从 \(u=A,v=B\) 往上跑。每次取出 \(fa(u),fa(v)\) 的较大者，放进当前的值域集合。
\(f_{x,y}\) 为左链有 \(x\) 层满二叉树，右链有 \(y\) 层满二叉树的合法概率，由 \(f_{x-1,y}\) 以及 \(f_{x,y-1}\) 转移。
设 \(u,v\) 分别在倒数第 \(A,B\) 层，则 \(f_{A,\ge B}=1\)。
根据引理，转移的系数就是钦定 \(fa(u)<v\) 以及 \(fa(v)>u\) 的概率成立的概率。
因此有 \(f_{i,j}=\dfrac{(2^i-1)f_{i-1,j}+(2^j-1)f_{i,j-1}}{2^i+2^j-2}\)。
复杂度 \(O(n^2\log \text{mod})\)，懒得写预处理逆元。
5. AT_abc240_h
先找性质。\(n\) 很奇怪。
注意到在一种最优方案中，长度为 \(x\) 的选出来的串存在当且仅当长度为 \(x-1\) 的串存在，因为如果是它大于 \(x-2\) 的某个串的字典序的话，这个的第 \(x\) 个字符没有存在的必要，可以删去。
因此最长的串长度 \(\leq \sqrt{2n}\)。
因此可以把所有长度为 \(1\sim \sqrt{2n}\) 的串都全部找出来。用 SA 上的 \(\text{height}\) 判断 \(\text{LCP}\) 以用字典序排序即可。
因此就是维护这个新串序列的，最长互不相交子序列，树状数组维护前缀 \(\min\) 即可。
时间复杂度 \(O(n\sqrt{n}\log n)\)。
6. UOJ748
称原串为 \(S\)。
考虑判断一个长度 \(n+2t\) 的串 \(T\) 是否合法，对于这个 \(01\) 串，采用以下的匹配形式：
从左往右扫字符串 \(T\)，维护一个指针 \(p\) 表示 \(S\) 与 \(T\) 当前匹配到的位置。如果这一位能匹配上，\(p\leftarrow p+1\)。若不能匹配，如果是 \(0\) 就扔到栈里面，如果是 \(1\) 就弹栈顶，这代表一个匹配。
比较厉害的是，如果栈为空也有可能合法。
考虑让 \(p\) 回退到最大的 \(g\)，使得在 \(g\) 之后的存在一个没有匹配的 \(0\)，也就是把 \(g\) 往后的都视为，尚未匹配。
dp 加速这个过程：\(f_{i,p,siz}\) 表示 \(T\) 的指针扫到 \(i\)，\(S\) 匹配位置为 \(p\)，栈的大小为 \(siz\) 的方案数。
答案就是 \(f_{n+2t,n,0}\)。
7. CF1728G
鉴定为容斥系数只留个奇偶，CF1943D2。
默认灯塔和点都有序。
显然有个容斥。\(f_S\) 表示钦定 \(S\) 集合恰好不被覆盖，容易将 \(n\) 个灯塔拆成 \(|S|+1\) 个区间。方案数容易计算，具体就是二分出控制区间，前缀积一下然后除一下就随便算了。这是 \(O(m2^m\log n)\) 的。
考虑动态咋做，也往恰好不被覆盖的点去想，注意到一个灯塔管的是一段区间，那么新增点不管的集合应该恰好是一段前缀一段后缀，这个是 \(O(m^2)\)，NOT \(O(2^m)\)。这个东西考虑怎么和 \(f_S\) 整合到一起去。令枚举的管辖不到的是 \([1,l]\cup [r,m]\)，这个新增的灯塔有 \(g_{l,r}\) 的方案（这个计算显然可以 \(O(1)\)），那么真正的 \(val_S\) 应该在保证 \(S\) 不被原来的覆盖的前提下，也不被新增点覆盖。考虑应该有 \(S\subset ([1,l]\cup [r,m])\)。
另一种表现形式是 \((l,r)\cap S=\empty\)。所以会想到，将 \(f_S\) 放在所有的间隔上统计。
统计答案，不关心 \(|S|\) 的具体大小，只关心奇偶性带来的容斥系数，所以只保留 \(|S| \bmod 2\) 即可。
就有了 \(val_{x,y,t}=\sum_{x\in S,y\in S,(x,y)\cap S=\empty,|S|\equiv t\pmod 2} f_S\)。
随便统计下就过了。提交记录
心情不好 不想算复杂度
8. P9596
支配对思想+放缩。
典爆了，直接扔到二维平面上 \((i,a_i)\)，那么就是看左上方点的个数的最大值。支配对思想搞一下，发现只有 \(a_i\) 取后缀 \(\min\) 才有用，否则就会被支配。
按照从小到大关系排序后得到 \(b_i\)，那么这个点的答案就是 \(i-b_i\)。可以离线离散化搞到 \(O(n)\) 的值域。
接下来从值的角度思考，注意到有用点的 \(b_i\) 一定递增，维护 \([1,b_i-1]\) 有值的个数 \(cnt\)，贡献显然就是 \(i-cnt\)。非后缀 \(\min\) 的点其实也可以扔上 \(i\) 的属性（放缩思想？？），不影响后面的点算贡献，因为它这样一搞的 \(b_i\) 是更大的。
这个东西可以线段树维护，\(O(n\log n)\)。具体就是：
node merge(node x,node y){ return (node){x.cnt+y.cnt,max(x.ans,y.ans-x.cnt)}; }
9. LOJ2743
差分思想+扫描线思想+连续段 dp。
考虑 \(a_i\) 是固定的，从大往小加点。继续考虑扔到二维平面上 \((i,a_i)\)，那么就是在维护扫描线的同时，记录正在下垂的线段以及已有线段的总长度，这个和连续段有关，所以就是连续段 dp 板子题。
分讨：
- 合并连续段
- 插入连续段中的某个端点
- 新增连续段
第一次碰这个东西，在学校想的时候，一直没有想明白是，这个状态本身不要记录具体位置。就考虑相对的 是否形成连续段 关系
\(f_{i,j,k,0/1,0/1}\)：当前考虑前 \(i\) 个数，形成了 \(j\) 个连续段，线段总长为 \(k\)，最左侧，右侧的连续段是否继续下垂（不能下垂则为 \(1\)，代表不能再新增）。
dp 过程中不考虑各连续段的状态如何，只考虑整体上存在多少个连续段，各连续段的状态的总和是多少。原博客
10. LOJ4092
考虑判断一个 \(\lbrace(a_1,b_1),(a_2,b_2),\cdots,(a_k,b_k)\rbrace\) 是否合法。
扔到二分图上去考虑。
二分图完美匹配，左部图是 \(a_1,a_2,\cdots,a_k\)，右部图是 \(b_1,b_2,\cdots,b_k\)。不妨设已经按照 \(a_i\) 进行排序。\((a_i,b_j)\) 有边当且仅当 \(a_i>b_j\) 且 \(i\ne j\)。
那么 \(N(\lbrace a_1\rbrace)\subseteq N(\lbrace a_2\rbrace)\subseteq \cdots \subseteq N(\lbrace a_n\rbrace)\)。
考虑：完美匹配存在的充分必要条件是任意左部图集合 \(S\)，有 \(|S|\leq |N(S)|\)（Hall 定理）
显然对于任意取一个集合 \(S\)，对于 \(a_i=\max(S)\)，将小于 \(a_i\) 的所有 \(a_j\) 扔进去 \(S\)，不会造成 \(N(S)\) 的改变，但是会造成 \(S\) 大小的改变。因此可以将左部图的前 \(i\) 个全部扔进去。
也就是说，对于任意 \(i\)，必须要有 \(\ge i\) 个 \(b_j\) 小于 \(a_i\)。
这个应该往值上去想了。
放到数轴上的判定条件就是 \([b_i,a_i]\) 只有包含或者相离的关系。
二维数点 \(O(n\log n)\) 离线求。具体就是找出左边第一个区间使得相交，右边第一个区间使得相交，然后扔到 \(x-y\) 平面上即可。
11. LOJ4042 / 「SNOI2024」公交线路
厉害数数题。
显然每条路径的端点放在叶子的限制是最强的，也就是考虑任何两个叶子节点 \(u,v\)，都可以在两步之内到达。令 \(S_u\) 为一度点 \(u\) 可以一步到达的点的集合。那么相当于任何 \(u,v\) 的 \(S_u,S_v\) 都存在非空交集。
因为两两有交集，而树无环，所以所有的 \(S_i\) 的交集不为空，记这个是集合 \(S\)。
注意到 \(S\) 构成一个连通块，可以考虑 点 - 边 容斥。
记 \(f_x\) 为 \(x\in S\) 的方案数，\(g_{(u,v)}\) 为边 \((u,v)\) 中 \(u,v\in S\) 的方案数。答案即为 \(\sum f_x-\sum g_{(u,v)}\)。容易发现对于一个连通块，在答案中恰好会被统计 \(1\) 次。（被 \(|V|\) 次统计，被减去 \(|E|\) 次，而树上 \(|V|=|E|+1\)）
考虑怎么求 \(f_x\)。注意到只有叶子节点的 公交路线 是在考虑范围之内的，我们要求每个叶子节点都可以到达 \(x\)。在树上 dp 时，考虑分为子树外的叶子以及子树内的叶子。
现在仅考虑通过 \(u\) 的连通块：
- 对于不经过 \(u\) 的路径，这种是简单的，压根不会关心是否连上，且可以通过统计子树大小快速计算，直接乘进贡献里面。
考虑容斥，钦定 \(u\) 不被 \(i\) 个叶子节点一步到达。令 \(f_{u,i}\) 表示使得 \(u\) 钦定不被 \(u\) 中的 \(i\) 个叶子节点到达。
做树上背包，暴力计算 \(u\) 子树外的连边方案数。
钦定 \((u,v)\) 被包含在连通块是，同样用容斥，但是 \((u,v)\) 同时不能被叶子节点就是要求没有叶子节点的路径跨过 \((u,v)\)，相当于 \((u,v)\) 将整个树断开，分别计算两个连通块的方案数即可。
钦定 \(i\) 个 \(u\) 中的叶子节点无法到达 \(u\)，那么剩下的 \(\text{size}(u)-i\) 的点就是不受限制的，计算方案数的柿子很长，懒得写。
柿子：
void dfs(int u,int fa=0){
if(deg[u]==1) return sz[u]=leaf[u]=1,void();
dp[u][0]=sz[u]=1;
int sum=0;
for(int v:g[u]) if(v^fa){
dfs(v,u),sum+=S(sz[v]);
vector<int>tmp(leaf[u]+1);
F(i,0,leaf[u]) tmp[i]=dp[u][i],dp[u][i]=0;
F(i,0,leaf[u]) F(j,0,leaf[v]) inc(dp[u][i+j],1ll*tmp[i]*C(leaf[v],j)%mod*qpow(2,(sz[u]-i)*(sz[v]-j))%mod);
sz[u]+=sz[v],leaf[u]+=leaf[v];
}
sum+=S(n-sz[u]);
int tot=0;
F(i,0,leaf[u]) {
int val=1ll*dp[u][i]*qpow(2,(sz[u]-i)*(n-sz[u]-(leafall-leaf[u])))%mod*qpow(qpow(2,sz[u]-i)-1,leafall-leaf[u])%mod;
if(i&1) dec(tot,val);
else inc(tot,val);
}
inc(ans,1ll*tot*qpow(2,sum)%mod);
if(!fa) return;
tot=0;
F(i,0,leaf[u]){
int val=1ll*C(leaf[u],i)*qpow(2,(sz[u]-i)*(n-sz[u]-(leafall-leaf[u])))%mod*qpow(qpow(2,sz[u]-i)-1,leafall-leaf[u])%mod;
if(i&1) dec(tot,val);
else inc(tot,val);
}
dec(ans,1ll*tot*qpow(2,S(n-sz[u])+S(sz[u]))%mod);
}
时间复杂度 \(O(n^2)\)。
12. LOJ3536 /「NOI2021」机器人
刻画成矩阵形式。
平衡树随便维护。
【李超树】
核心思想就是标记永久化，线段树维护 \(x\in[l,r]\) 时，\(x=\text{mid}\) 的最优决策直线。然后判断 \(f(l),f(r)\) 与当前决策直线在此位置的值的大小关系，决定是否递归下去。
13.1. LOJ2032
树剖维护李超树。
13.2. LOJ2483
李超树可以解决横坐标不单调的斜率优化 dp。多一个 \(\log\)，烦人程度比凸包队列写法好多了。
14. 正睿 省选 23 Day10 T1
多次给定 \(k\)，求所有 \([l_i,r_i+kv_i]\) 的并，\(q,k\leq10^6\)。
考虑把最开始的连续段扔在一起解决，就是按照 \(l_i\) 排序。然后插入在这个连续段末尾前的所有的直线 \(y=v_ix+r_i\)。二分找到最大的时刻 \(p\) 使得 \(\max(f(p))\) 小于下一个线段左端点。
然后每个连续段形如一次函数，总的只有 \(O(n)\)，因此每次暴力二分找这个连续段的右端点的复杂度是 \(O(n\log^2n)\)。二次差分容易维护。
15.「北大集训 2021」末日魔法少女计划
披着个构造皮子的 dp 题。
讲课讲了这题，感觉很厉害啊。
注意到 \(A_{i,j}=1\) 的点对 \((i,j)\) 可以改写成一张有向图上 \(i\to j\) 的边，考虑把这张图建出来。那么 \(\forall i,j:(A^k)_{i,j}=1\) 的意思就是存在一条路径，使得 \(i\) 到 \(j\) 经过不超过 \(k\) 条边。现在我们就是要构造这张有向图上的非平凡边（\(i\to i+1\) 都是给出的）。
评分标准告诉我们存在一种方案，\(m\leq nf(k)\)。\(0.9\leq f(k)\leq 8\)。大概边数要做到 \(O(n)\)，这其实很困难，但这引导我们去往最小化边数去思考。
\(\bm{k=2}\) 怎么做？
显然就是分治：对于每个 \([l,r]\)，\([l,mid-1)\) 都向 \(mid\) 连边，\(mid\) 都向 \((mid+1,r]\) 连边。分治解决 \([l,mid),(mid,r]\) 即可。这样的边数恰好满足 \(m\leq nf(2)\)。
\(\bm{k=3}\) 怎么做？
注意到 \(mid\) 是个很厉害的性质，然而只找一个有点亏，依旧考虑当前区间 \([l,r]\)，我们可以找两个关键点 \(a,b\)，使得区间被划分为 \([l,a),(a,b),(b,r]\)。我们考虑 \(a,b\) 都往相邻的区间中的所有点都连边，并且连接边 \(a\to b\)，这样可以得到比猫树分治做法更优的解。
注意到这个关键点可以选不止一个，其实可以选任意 \(t\) 个，设为 \(p_1,p_2,\cdots,p_t\)，此时被分割成的若干段区间内部都满足相同子结构性质。也就是说，\(\forall i,(p_i,p_{i+1})\) 的区间的划分是递归进行的，相同子结构的问题（定义 \(p_0=l-1,p_{t+1}=r+1\)）
注意到要保证两两能跳到，因此 \(p_1,p_2,\cdots,p_t\) 这些关键点之间两两都必须有边，此时会多产生 \(\dfrac{t(t-1)}{2}\) 的代价。
\(\bm{k>3}\) 怎么做？
注意到关键点之间两两需要保证在 \(k-2\) 步之内可以互相抵达，这同样可以被归类为一个长度为 \(t\)，\(K=k-2\) 的子结构。
算法设计
上面一车东西都是「在 \(n\) 个点的图中，\(k=t\) 时最少需要添加多少条边」的子结构，直接把这个写成 dp，记为 \(f_{t,n}\)。
转移按照 \(k\) 从小往大进行，每次枚举一个长度 \(n\)，然后枚举关键点个数 \(t\)。
考虑关键点内部怎么划分。注意到我们要求中间划分出来的段尽量均摊，调整法理解一下就会发现这是对的，但是两边与中间的贡献是不平衡的，我们只能保证两边选出来的数量尽量一致，不能去考虑与中间的一致，之前在这里卡了半天。
因此考虑一个「辅助情况」：两边都划分为 \(0\) 个，直接钦定 \(p_1=l,p_t=r\)，中间直接被划分为 \(t-1\) 段。此时可以刻画出来每一段的长度，就是直接均摊。继承子结构的贡献之后，然后加上这一层关键点对两边区间的新边，以及关键点之间的边的数量。
然后你发现，枚举两边的点的个数相等为 \(h\) 时，减去两侧的点之后，就是一个规模为 \(n-h\) 的「辅助情况」的解。
这样容易将一层的 dp 做到 \(O(n^2)\)，总共 dp 的复杂度就是 \(O(n^2k)\)。
构造方案？直接由最后的 dp 值倒序进行整个 dp 过程，找到每个 dp 值是从哪里来的，输出每一次产生的新的贡献的边即可。
16.「PA 2024」Kraniki
由期望的线性性，可以将每个位置拆开来算，考虑有 \(f_i\) 个点放水会流到 \(i\)，那么 \(i\) 需要打开当且仅当，在打开的顺序中，它比这些 \(f_i\) 个点都靠前，所以有 \(\dfrac{1}{f_i}\) 的概率打开。显而易见，每个位置求和，答案就是 \(\sum_{i=1}^n \dfrac{1}{f_i}\)。
考虑求 \(f_i\)。考虑写成有向图的形式，\(i\) 的连边最多有两条：往左边流第一个流到的，往右边流第一个流到的。如果有重复则需要只保留一条。找两端的后继，可以直接线段树实现。
建出来之后，\(f_i\) 就是在这张图上可以抵达 \(i\) 的点的个数。考虑到 \(n\) 是无入度点，所以可以从 \(n\) 开始自顶往下 dp，初始就是 \(f_i=1\)，因为是有它自己。转移显然有往后继 \(v_l,v_r\) 都加上 \(f_u\)。如果有两个后继，需要在它们第一次共同流到的位置减去 \(f_u\)，不然会出现重复。
怎么找第一次共同流到的位置呢？其实就是支配树上 \(v_l,v_r\) 的 \(\text{LCA}\)。我写的做法是，直接二分这个位置 \(k\)，分别倍增左右链跳到第一个 \(k\) 之上的点，判定是否有当前位置在目标位置之下，看一下是否满足 \(R_{u'}>L_{v'}\)。（\(L_i,R_i\) 是输入给定的线段），关于这个式子的解释：如果没有交点，它不会成立。正是因为有了这个交点，才导致，右侧尽量往左的水流的位置 \(<\) 左侧尽量往右的水流。它们第一次相交就是在目标位置。
时间复杂度 \(O(n\log^2n)\)。
17.「APIO 2021」雨林跳跃
对于 \([c,d]\)，其实可以只关心位置以及最大值，因为它的拦截能力最强。
显然可以单调栈 \(O(n)\) 扫出来前驱后继，记录为 \(pre_i,nxt_i\)。
考虑一直往右跳一定会经过 \(\argmax(b\sim c-1)\)，我们要研究关键点 \(\argmax(b\sim c-1)=p\)。
显然我们可以要么从后面开始，从上方划过去 \(p\)，要么经过 \(p\)。这两种方式都会保证纵坐标 \(>a_p\)。因此需要有 \([c,d]\) 中的来拦截。所以有解需要 \(\max(b\sim c-1)<\max(c\sim d)\)。
注意到 \(p\) 总是要间接或者直接去被考虑的。因此有两种情况：经过 \(p\) 和不经过 \(p\)。
经过 \(p\) 时，最后一步显然可以一步跳到 \([c,d]\) 里面去。考虑怎么找 \(p\)。起初我以为往左跳是没用的，但后来发现往左可以帮助你略过一堆无意义的向右一直走。原本需要走 \(43\) 步，可能往左只需要 \(23\) 步。
当起点找到的时候，一定是会从起点开始，不断向 \(pre,nxt\) 中 \(a_i\) 更高的点跳，直到两者中 \(\max\) 高度 \(>\) 终点高度。这样你发现其实是，要较少步数跳到 \(p\) 的话就要尽量拔高初始高度，容易发现直接取 \(\argmax(\max(pre_p+1,A)\sim B)\) 就行了。然后倍增先跳 \(<a_p\)，再往右，也可以倍增维护。
不经过 \(p\) 时，最后一步可以直接从 \(pre_p\) 走过去，类似倍增，优化每步尽量走高的策略。
启示：找终局状态前的一步，以及大胆贪心猜结论。从位置和值的两方面思考。从一个条件背后去找关键的突破口。
18.「APIO 2021」封闭道路
\(f_{u,0/1}\)，\((u,fa_u)\) 是否保留，使得 \(u\) 子树全部合法的最小代价。这个转移就是先保留所有 \(f_{u,1}\)，然后取最小的若干个变化量最小的值，使得 \(u\) 度数满足要求。
显然对于给定的 \(k\) 可以随便做到 \(O(n^2\log n)\)，正解就是希望把 \(k\) 从小到大之间建立联系。不难发现如果小往大，那么有用的点是越来越少的，然后进而对后面产生一定的贡献。
将度数 \(\ge k\) 的称之为有用点，反之为无用点。\(k\) 扫描线，每次找连通块，跑这个 dp。
考虑有用点 \(u\) 和无用点 \(v\) 之间的决策，那么 \(v\) 对 \(u\) 的贡献后面一直不变为 \(w\)，考虑用一个可删堆存每个点旁边连的无用点的边，复杂度 \(O(n\log n)\)。
对于每个点复杂度分析得到均摊 \(O(n\log n)\)，\(\log\) 是因为堆。
19.「GDKOI-S 2023」游戏
考虑放在路径交点上解决问题，容易发现这是三维偏序问题，离线即可。
怎么直径选点可以过啊？？
\(O(n\log n)\)。
标签：sz,Set,leaf,log,text,Solution,考虑,dp From： https://www.cnblogs.com/nullptr-qwq/p/18236459