B 题
题目描述
给定一个长度为 \(N\) 的数组 \(A\), 问有多少个区间 \([L, R]\) 使得 \((\min \limits_{i = L}^R\) \(A_i)\) = \(y\), \((\max \limits_{i = L}^R\) \(A_i)\) = \(y\)
思路
可以发现, 对于任意一个合法的段, 里面绝对没有 \(< y\) 或 \(> x\) 的元素, 所以可以给所以连续的 \(\le x, \ge y\) 的元素分成一段
对于一段 \([A, B]\) 的一段
枚举左端点 \(i \in [A, B]\)
我们给以找到最小的 \(L \in [A, B]\), 满足 \((\min \limits_{i = A}^L\) \(A_i)\) = \(y\), \((\max \limits_{i = A}^L\) \(A_i)\) = \(y\), 此时的可行右端点的数量为 \(B - L + 1\)
双指针维护即可
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int x, y, n, k, a[N], cnt[3], b[N];
long long ans;
int main(){
cin >> n >> x >> y;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
for(int i = 1, j; i <= n + 1; i++){
if(a[i] > x || a[i] < y){
for(j = i - 1; a[j] <= x && a[j] >= y; j--){
b[j] = i - 1;
}
}
}
for(int i = 1, j = 1; i <= n; ++i){
for(j = max(j, i); a[j] <= x && a[j] >= y && (!cnt[0] || !cnt[1]); j++){
cnt[0] += a[j] == x, cnt[1] += a[j] == y;
}
if(cnt[0] && cnt[1]){
ans += b[i] - j + 2;
}
cnt[0] -= a[i] == x, cnt[1] -= a[i] == y;
}
cout << ans;
return 0;
}