• 欢迎光临~

DTOJ #5860. 麻烦的杂货店 题解

开发技术 开发技术 2022-06-04 次浏览

给定一个长度为 (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)) 解决。

DTOJ #5860. 麻烦的杂货店 题解

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

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

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

程序员灯塔
转载请注明原文链接:DTOJ #5860. 麻烦的杂货店 题解
喜欢 (0)