括号匹配是经典的哈希结构，如果带修就变成 CF1340F 了，但是这里不带修，允许我们使用更简单的结构刻画。

本质是每个区间只会剩下一段左括号或者右括号或者为空，不妨先考虑剩下左括号，右括号只需要翻转括号序列和左右括号种类再做一遍即可，为空可以并进剩下左括号考虑。

考虑按右端点扫描线，每次将新的括号压入栈中并维护栈中括号的哈希值。如果扫到一个位置在 $i$ 右括号无法匹配，说明对于所有 $l\le i$ 都完蛋了。一个区间加单点查询的数据结构即可完成哈希值的维护。

对于询问，在栈中二分出左端点的位置，即哪些左括号在 $[l,r]$ 的范围内。但一个问题是这个区间内的右括号可能已经和 $<l$ 的左括号匹配了，我们要维护右括号所匹配的左括号位置的最小值来判断这个区间是否合法。这里使用了一个单点修改区间查询最小值的线段树。

代码。