T1
做了 \(3h\)，时间复杂度不对，小样例都还有一个没过。
考虑容斥，不连通的情况枚举 \(1\) 号点所在连通块。
设 \(f_{S, i}\) 表示 \(S\) 连通且选了 \(i\) 条边的方案数。
设 \(inb_s\) 表示 \(S\) 内部的边数。
那么有转移：
\[f_{S,i}=\binom{inb_S}i-\sum_{T\subsetneqq S,1\in T}\sum_jf_{T,j}\binom{inb_{S\setminus T}}{i-j} \]暴力转移复杂度 \(O(3^nm^2)\)，难以通过。
可以将 \(f_S\) 看成多项式，那么转移就是：
\[f_S=(x+1)^{inb[S]}-\sum_{T\subsetneqq S,1\in T}f_T\cdot(x+1)^{inb[S\setminus T]} \]换元，令 \(x'=x+1\)，后面部分的乘法就变成了平移，可以 \(O(m)\) 解决。总时间复杂度 \(O(3^nm)\)。
T2
本来就没有准备打这道题的高分或者正解。打了一个不能证明正确性的贪心拿了和输出 NO 一样的分。
和差相关，考虑差分。令 \(c_i=a_{i+1}-a_i\)。那么 \(b_i=\max\{|c_i|,|c_{i+1}|,|c_i+c_{i+1}|\}\)。
设 \(dp_{i,x}\) 表示考虑了前 \(i\) 个数，\(c_i=x\) 是否合法。转移可以写成这样：
| \(c_i\) | \(\longrightarrow\) | \(c_{i+1}\) |
|---|---|---|
| \(b_i\) | \(\longrightarrow\) | \([-b_i,0]\) |
| \((0,b_i)\) | \(\longrightarrow\) | \(b_i-x,-b_i\) |
| \(0\) | \(\longrightarrow\) | \(b_i,-b_i\) |
| \((-b_i,0)\) | \(\longrightarrow\) | \(-b_i-x,b_i\) |
| \(-b_i\) | \(\longrightarrow\) | \([0,b_i]\) |
可以发现转移关于 \(0\) 对称，初始状态也关于 \(0\) 对称，所以可以只看一半。
修改一下状态表示，设 \(dp_{i,x}\) 表示考虑了前 \(i\) 个数，\(|c_i|=x\) 是否合法。转移就长这样：
\[[0,b_i)\longrightarrow b_i-c_i,b_i\\ b_i\longrightarrow [0,b_i] \]发现 \(dp_i\) 由一个区间和若干单点组成，区间维护左右端点，单点用双端队列维护即可。复杂度 \(O(n)\)。
T3
打了一个 \(O(nq)\) 的 Z 函数。就莫名其妙多了 \(10pts\)。
设 \(lcp(i,j)\) 为原串中后缀 \(i,j\) 的最长公共前缀。
答案为 \(\sum_{i=L}^R\min(R-i+1,lcp(L,i))\)。
将序列倒过来建一个 SAM，两个后缀的 lcp 就是它们在 parent tree 上的 LCA 的 len。
考虑点分治。先将每个询问挂到它的左端点对应的节点上。设当前分治中心为 \(rt\)，要统计 \(L\) 到 \(i\) 的路径（过 \(rt\)）答案。分类讨论：
-
如果 \(rt\) 在 \(LCA\) 到 \(i\) 的路径上，此时 \(LCA\) 只与 \(L\) 有关。可以统计和每个 \(L\) 对应 \(i\) 的答案，线段树乱搞。
-
如果 \(rt\) 在 \(LCA\) 到 \(L\) 的路径上，此时 \(LCA\) 只与 \(i\) 有关。可以考虑每个 \(i\) 对那些 \(L\) 作贡献，转化为二维数点。、
总时间复杂度 \(O(n\log^2n)\)。
标签：rt,复杂度,暑期,20230718,sum,LCA,longrightarrow,集训,inb From： https://www.cnblogs.com/dks-and-xiao-yu/p/17564148.html