(题解由比赛出题人提供,点击右侧“本文相关内容”的题目即可开始做题)
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
全部评论
(0) 回帖