专项测试数据结构1

式子懒得写，写几个比较重要的地方吧

\(\phi(a* b)=\frac{\phi(a)* \phi(b)* \gcd(a,b)}{\phi(\gcd(a,b))}\)，就把\(\phi(x)=x\prod_{p|x}\frac{p-1}{p}\)代进去就行了

然后枚举gcd=d，出来一个恰好的形式长这样

\[\sum_{i=1}^{n}\sum_{j=1}^{n}[\gcd(a_i,a_j)=d]* \phi(a_i)* \phi(a_j)* dis(i,j) \]

这个记为f[d]

然后莫反，\(F_x=\sum_{x|d}f_d，f_x=\sum_{x|d}F_d*\mu(\frac{d}{x})\)

那么这个F[x]就能写成至少的形式

\[\sum_{i=1}^{n}\sum_{j=1}^{n}[d|\gcd(a_i,a_j)]* \phi(a_i)* \phi(a_j)* dis(i,j) \]

把d的倍数取出来建虚树，然后树形dp就行了

拿哈希过的，，

O(nm)是过不去的（反正我过不去）

就剪剪枝，拿个map，mp[i]存前缀哈希为i的映射值，映射到vector上存串的下标

然后前缀已经配好了，数一数这些串的后缀几个能配上就行了

正解还是很多的，其中之一

按前缀排序，那么前缀能匹配上的串区间二分就行了，匹配后缀就可持久化trie，然后把询问后缀串放trie上跑。

题解给的复杂度是\(O(m\log n+L1+L2)\)，要是我写，L1得带个log(拼一块后缀数组)

考虑维护\(c_i\)表示以 i 为右端点的子串最大值，拿个优先队列存(i,c[i])，每次取队头，再插入(i,c[i]的次大值)

问题变成了维护\(c_i\)，查询次大值转换成支持删除和查询区间最大值，不难想到线段树

可持久化一下就行了，i-1->i时，只需将\([last_{a_i}+1,i]\)加上a[i]

相关