E - Max Min Editorial by carrot46
整数の組 \((L, R)\) が条件を満たすのは、以下の 2 条件が共に成立する時です。
- 区間 \([L, R]\) の中に \(X, Y\) がそれぞれ \(1\) つ以上存在する。
- 区間 \([L, R]\) の中に \(Y\) 未満の要素や \(X\) より大きい要素が存在しない。
1 つ目の条件は、区間 \([1, R]\) の中で最も右にある \(X, Y\) の位置をそれぞれ \(\mathrm{pos}_X, \mathrm{pos}_Y\) (存在しないなら \(0\) ) として、\(L \leq \min(\mathrm{pos}_X, \mathrm{pos}_Y)\) であることと同値です。
2 つ目の条件は、区間 \([1, R]\) の中で最も右にある「 \(Y\) 未満または \(X\) より大きい要素」の位置を \(B\) (存在しないなら \(0\) ) として、\(B < L\) であることと同値です。
よって、\(\mathrm{pos}_X, \mathrm{pos}_Y, B\) を更新しつつ、\(R = 1, \dots, N\) の順に条件を満たす \(L\) の個数を求めれば良いです。
実装例 (C++) : https://atcoder.jp/contests/abc247/submissions/30895819
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, X, Y;
cin>>N>>X>>Y;
vector<int> a(N);
for(int i = 0; i < N; ++i) cin>>a[i];
int posX{-1}, posY{-1}, B{-1};
long long res{};
for(int i = 0; i < N; ++i) {
if(a[i] == X) posX = i;
if(a[i] == Y) posY = i;
if(a[i] < Y or X < a[i]) B = i;
res += max(0, min(posX, posY) - B);
}
cout<<res<<endl;
}
posted:
last update: