(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）

T1 旅游观光
输出(n-1)/2
构造和样例解释类似

T2 栈和排序
维护一个后缀max,f[i]表示[i..n]的max的位置
每次push(i)时，如果a[f[i]] > a[i]，就把[i+1..f[i]]都push进去
否则pop(i)
可以证明这样是最优的

T3 最长回文
对a、b各做一次manacher。
枚举一个串的回文中心p作为最后拼出来的串的回文中心
有个结论是我们只需要考虑以p为中心的极长回文串
然后二分答案，hash来check在另一个串里面最多选多长的串
O( nlogn )

T4 字符串操作
暴力

T5 数列查找
可以考虑进行高维离散化
比如说，对于一个数x，其在序列中出现了y次
开个vector v[ MAXN ]
在v[1] , v[2] ... v[y]中都push_back( x )
然后对于每个vector，分别进行离散化
这样就保证了空间线性
在高维离散化的基础上进行值域分块，然后跑莫队即可
O( nsqrtm + msqrtn ) = O( msqrtn )

T6 序列查询
先考虑单次询问怎么算
对于数x，假设出现了y次，区间长度是len
则x对答案的贡献是x( ( -1))=x( - )
是除了x之外的数有这么多个不同的子序列，这些对x的贡献没有影响
-1 是所有x构成的子序列中有 -1种至少包含一个x，有1种不包含x
如果每次模数一样的话，直接边跑莫队维护就可以了。。。
然而出题人想恶心你，所以每次模数不一样
注意到贡献分为两部分x 与-x 其中第一部分非常好维护第二部分的贡献，可以把出现次数相同的数一起维护贡献注意到一起区间中只有O( sqrt( n ) )种不同的出现次数因为1+2+...+sqrt(n) = O(n)这是一个自然根号所以我们可以用一个均摊的莫队来维护区间可能的出现次数，从而维护区间中所有出现次数然后为了O(1)实现快速幂，我们可以每次O( sqrt(n) )算出2^1,2^2…2^sqrt(n) % p以及2^sqrt(n),2^2sqrt(n)…2^sqrt(n)sqrt(n) % p

总复杂度O( nsqrtm + msqrtn ) = O( msqrtn )

• 其他疑问可加以下交流群（加入一个即可啦~）
  牛客多校算法训练营1：453799454
  牛客全国算法训练营2：330766563
  牛客多校算法训练营3：934889305

*