为什么全场切我不会？为什么全场切我不会？为什么全场切我不会？
首先因为题目中要求左括号个数，我们就来关注一下左括号。
对于一个左括号，假设它右边是右括号，那么这个左括号就会往右走，否则不会往右走。随便选个左括号开始标号，往左为负，往右为正，设 \(p(k,i)\) 表示第 \(i\) 个左括号在第 \(k\) 阶数列中的位置，那么有递推关系 \(p(k+1,i)=\min(p(k,i)+1,p(k,i+1)-1)\)，一直递推到 \(k=0\) 就是 \(p(k,i)=\min\limits_{i\leq j\leq i+k}(p(0,j)+k-2(j-i))\)，如果左括号的个数大于长度的一半，可以反转整个序列和序列的内容，以及询问，那么只需要处理 \(2n\) 范围内的 st 表就可以查询某个数的位置了。
对于每个询问二分出第一个在这个区间内的左括号和最后一个在这个区间内的左括号即可。时间复杂度 \(O(n\log n+q\log V)\)。
标签：全场,往右,leq,Sequence,括号,Infinite,QOJ From： https://www.cnblogs.com/275307894a/p/17697568.html