牛客国庆集训派对Day1___J Princess Principal —— 思维 | 线段树 | RMQ

题目链接：点我啊╭(╯^╰)╮

题目大意：

    给出一个长度为 $n$ 的括号序列，括号有多种，问区间$（l，r）$内的括号是不是完全匹配的？？？

解题思路：

①：用栈来存储，同时记录到第 $i$ 个括号时，它的状态是怎样的，即当前括号的 $a[i]$ 值。
       那么我们就对 未加入所求序列时的状态 $a[l?1]$ 和 加入所求序列后的状态 $a[r]$ 进行判断，如果状态相同，证明这个区间内的括号相互“消掉了”，即区间内括号完全匹配

②：仍然用栈来存储，由于匹配方式是唯一的，我们用一个数组 $b[i]$ 来记录第 $i$ 个括号所匹配的括号的位置。若一个区间内的括号完全匹配，当我们从区间内取出一个单括号时，它所匹配的括号也必然在这个区间内，这种性质称为“封闭性”。
       然后我们预处理每个括号所匹配括号的位置即$b[i]$，但是查询的时候复杂度仍然是线性的。然而我们只需要对区间$（l，r）$求所匹配的括号位置的最值进行查询即可，换言之，若区间$（l，r）$所匹配的括号的最大值或者最小值不在$（l，r）$里，那么就违反了“封闭性”。问题就转换成了求区间最值，我们可以采用RMQ或线段树解决。

代码思路：

    这里给出第一种方法 和 第二种采用RMQ来实现的代码，注意题目所给出的括号类型的判断

核心：标准的括号匹配，这里对区间进行询问，可以转化为求区间最值，当然几种方法都熟练的话直接判断一下状态即可

①：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;int n, m, q;
int a[maxn], x[maxn];	//x表示状态 
stack <int> s;int main() {scanf("%d%d%d", &n, &m, &q);while(!s.empty()) s.pop();for(int i=1; i<=n; i++)scanf("%d",a+i);for(int i=1; i<=n; i++) {if(s.empty()||!(a[i]&1))s.push(i);else if(a[s.top()]+1==a[i])s.pop();else s.push(i);if(s.empty()) x[i]=0;else x[i]=s.top();}while(q--) {int l,r;scanf("%d%d", &l, &r);if(x[l-1]==x[r])printf("Yes\n");else printf("No\n");}return 0;
}

②：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;int a[maxn], b[maxn];
stack <int> s;int dp_max[maxn][20], dp_min[maxn][20];
void ST(int n, int d[]) {for (int i=1; i<=n; i++) {dp_max[i][0] = d[i];dp_min[i][0] = d[i];}for (int j=1; (1<<j) <= n; j++) {for (int i=1; i+(1<<j)-1 <= n; i++) {dp_max[i][j] = max(dp_max[i][j-1], dp_max[i + (1<<(j-1))][j-1]);dp_min[i][j] = min(dp_min[i][j-1], dp_min[i + (1<<(j-1))][j-1]);}}
}
int RMQ_max(int l, int r) {int k = 0;while ((1<<(k+1)) <= r-l+1) k++;return max(dp_max[l][k], dp_max[r - (1<<k)+1][k]);
}
int RMQ_min(int l, int r) {int k = 0;while ((1<<(k+1)) <= r-l+1) k++;return min(dp_min[l][k], dp_min[r - (1<<k)+1][k]);
}int main() {int n,m,q;scanf("%d%d%d", &n, &m, &q);while(!s.empty()) s.pop();for(int i=1; i<=n; i++) {scanf("%d", a+i);b[i] = -1;if(s.empty()||!(a[i]&1))s.push(i);else if(a[s.top()]+1==a[i]) {b[i] = s.top();b[s.top()] = i;s.pop();} else s.push(i);}ST(n, b);while(q--) {int l, r;scanf("%d%d", &l, &r);if(RMQ_max(l, r)<=r && RMQ_min(l, r)>=l)printf("Yes\n");else printf("No\n");}return 0;
}