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))。