关于 括号序列与问号 问题的一类处理方法

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132548658

启发题： https://codeforces.com/gym/104531/problem/I

判断 str[l:r]str[l:r] 是否合法：

  1. 把所有 ? 替换成 ‘(’，然后前缀和记为 ss ，满足任意时刻 si≥sl−1s_i\ge s_{l-1}

  2. 把所有 ? 替换成 ‘)’，然后后缀和记为 tt ，满足任意时刻 ti≥tr+1t_i\ge t_{r+1}

注意，这是一个 充要条件 （在 r−l+1r-l+1 为偶数的情况下）

分析题目时可以把 s,ts,t 通过单调栈维护来弄一下奇奇怪怪的操作。