ABC247E - Max Min

考え方

区間$[1, N]$を，区間$[i, j]$で

• $X \leq A_{k} \leq Y \:(\forall k \in [i, j])$

を満たすものに分割して考える．あとはこの区間ごとに個数を数えれば良い．

区間の左端を$L = i$に固定して，$X, Y$の両方が出てくるまで右端を一つずつすすめる．初めて条件を満たす右端が$R = k$であれば，$L = i$の場合の数は$j - k + 1$．左端を1ずつ進めて，同じことを繰り返せば$L = i,i+1,...,j$のすべての個数を計算できる．

回答例

N, X, Y = map(int, input().split())
A = list(map(int, input().split()))

def f(l, r):
    cnt = 0
    L, R = l, l
    X_cnt, Y_cnt = 0, 0
    while L < r:
        while R < r and (X_cnt < 1 or Y_cnt < 1):
            X_cnt += (A[R] == X)
            Y_cnt += (A[R] == Y)
            R += 1
        if l <= L < R <= r and X_cnt > 0 and Y_cnt > 0:
            cnt += r - R + 1
        X_cnt -= (A[L] == X)
        Y_cnt -= (A[L] == Y)
        L += 1
    return cnt

ans = 0
l, r = 0, 0
while r < N:
    while l < N and (not (Y <= A[l] <= X)):
        l += 1
    r = l
    while r < N and (Y <= A[r] <= X):
        r += 1
    if 0 <= l < r <= N:  # i ∈ [l, r) => Y <= A[i] <= X
        ans += f(l, r)
    l = r

print(ans)

しゃくとり法は，dequeを使うと添字で混乱せずにすむ（ただ，今回はwhile q or q2:の部分がややこしいかも．．．）．

from collections import deque

N, X, Y = map(int, input().split())
A = deque(list(map(int, input().split())))

def f(q):
    cnt = 0
    X_cnt, Y_cnt = 0, 0
    q2 = deque()
    while q or q2:
        while q and (X_cnt < 1 or Y_cnt < 1):
            R = q.popleft()
            q2.append(R)
            X_cnt += (R == X)
            Y_cnt += (R == Y)
        if X_cnt > 0 and Y_cnt > 0:
            cnt += len(q) + 1
        L = q2.popleft()
        X_cnt -= (L == X)
        Y_cnt -= (L == Y)
    return cnt

ans = 0
while A:
    q = deque()
    while A and (not (Y <= A[0] <= X)):
        a = A.popleft()
    while A and (Y <= A[0] <= X):
        a = A.popleft()
        q.append(a)
    ans += f(q)

print(ans)