脚本宝典收集整理的这篇文章主要介绍了DTOJ #5860. 麻烦的杂货店 题解，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

给定一个长度为 (N) 的括号序，有 (M) 次询问，每次询问区间 ([L,R]) 内最长连续合法括号序列。

首先提供看见 括号序列 的一个思路：记左括号为 (1)，右括号为 (-1)，前缀和序列为 ({s_n})。这样一段连续区间 ([l,r]) 合法当且仅当：

1. (s_{l-1}=s_r)
2. (min_{lle ile r}{s_i}=s_r\)

我们考虑一个查询 ([L, R])：

记 (S = min_{L-1le ile R}{s_i})，找到 (u) 和 (v) 使得 (u) 是从左到右第一次碰到的 (S)，(v) 是从右到左第一次碰到的 (S)，显然 ([u+1,v]) 是合法的。此步可用 st 表，并记录下转移的所有可能位置中最左和最右，(O(nLOG n)) 解决。

然后考虑 ([L,u-1]) 和 ([v+1, R]) 是否有其他合法解。

求 Right[i] 为从 (i) 最多向右延申多少，Left[i] 反之。利用合法括号序的定义（(A) 或 AB），此步可以用栈 (O(n)) 解决。

然后 st 表，处理出区间最大 Right 和 Left。此时 ([L, u-1]) 的最优解即为 (max_{Lle ile u-1}{operatorname{Right}_i})，对于 ([v+1, R]) 同理。到此，查询可 (O(1)) 解决。总复杂度 (O(Nlog N + M))。

脚本宝典总结

以上是脚本宝典为你收集整理的DTOJ #5860. 麻烦的杂货店 题解全部内容，希望文章能够帮你解决DTOJ #5860. 麻烦的杂货店 题解所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。