考试不在状态
码题的时候根本不知道自己在码什么
$T2$转移写少暴露出对$SAM$理解不深刻
不
根本没有理解
感觉吃枣药丸
标签：
根号思想
题解：
不难发现式子其实是个等比数列求和
直接模拟显然会被菊花图卡
考虑对于每个点按度数是否大于$\sqrt{n}$分为重点和轻点
对于每个点$x$维护$g[x]$代表周围所以轻点的贡献和
每次轻点更改时暴力把周围的$g$更新
对于重点在操作$x$时暴力统计即可
复杂度$O(n\sqrt{n})$
标签：
$SAM$+$DP$
题解：
暴力建出$SAM$在$SAM$和$fail$树上$Dp$是$O(n^2)$
其实不必存储当前的长度
因为继续往下走的单次贡献一定没有当前的优
所以贪心在当前点操作到最长的长度即可
复杂度$O(m)$,$m$为$SAM$和$fail$树上的边数
标签：
$BIT$的神仙题
题解：
一道$BIT$题打了200行+
可怕～
但这题的思路很棒
首先$LIS$和$LDS$的重复部分最多为$1$
考虑求出经过每个点的$LDS$个数$g[i]$
设
$$all=\sum\limits_{i=1}^{n}g[i]$$
那么一个$LIS$集合${a_1,a_2...a_k}$
设
$$val=\sum\limits_{i=1}^{k}g[a[i]]$$
这个$LIS$不合法当且仅当$val=all$
所以问题转化为了求出一个$LIS$序列满足$val!=all$
限制很单一，只要不等于就OK
所以可以对于每个点维护两个不同的$val$的方案
最后便一定有一个是合法的
原文：https://www.cnblogs.com/AthosD/p/12188616.html