【题解】牛客练习赛11

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

T1 假的线段树
暴力

T2 假的字符串
每一个串如果有一个串是它的前缀，则肯定不行
否则每次从这个字母向同一个父亲的其他字母连边，表示这个大小关系必须存在
如果出现环，就出现矛盾了
可以通过拓扑排序找环
O( n + |s| )

T3 真的字符串
考虑用后缀平衡树维护这个序列即可
有两种写法
O( qlog^2n + |s1|logn )
O( qlogn + (|s1|+|s2)logn )

T4 求距离
暴力

T5 求最值
可以转换为平面最近点对
O( nlogn )
由于平面最近点对有1w种乱搞做法，根本不可能全部卡掉
我就用脚造的数据

T6 求子树
肯定是按照DFS序转换为区间查询
两个区间不好维护，但是这个信息具有可减性
可以考虑差分

按照DFS序转换为区间查询
然后考虑差分
[l1,r1] - [l2,r2]的询问
可以差分为：
F(l1,r1,l2,r2)=F(1,r1,1,r2)-F(1,l1-1,1,r2)-F(1,r1,1,l2-1)+F(1,l1-1,1,l2-1)
这样都变成了前缀的区间
就可以在这个上面跑莫队了

这个题m=5e5，然后这个差分会导致最多差分出9个询问
询问最后有5e6个左右，排序的O( mlogm )比较慢
可以考虑对莫队的询问进行基数排序
总复杂度O( nsqrt( m ) + m )

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