길이가 $N$인 순열 $A$와 두 상수 $p_1, p_2$가 주어진다. 인덱스 쌍 $(i, j)$ ($i < j$)에 대해 다음 조건 중 하나를 만족하면 해당 쌍은 정해진 점수를 기여한다:

• 조건 1: $j = i + 1$이거나, 구간 $(i, j)$ 내 모든 원소가 $\min(A_i, A_j)$보다 크거나 같으면, 기여도는 $p_1$이다.
• 조건 2: $\min(A_i, A_j) < \max_{k \in (i,j)} A_k < \max(A_i, A_j)$이면, 기여도는 $p_2$이다.

총 $m$개의 질의가 주어지며, 각 질의는 구간 $[l, r]$에 대해 $l \le i < j \le r$인 모든 쌍의 기여도 합을 묻는다.

핵심 아이디어

인접한 쌍 $(i, i+1)$은 항상 조건 1을 만족하므로, 각 질의마다 $O(1)$로 처리 가능하다. 따라서 본문에서는 $j > i+1$인 쌍만 고려한다.

이러한 쌍 $(i, j)$에 대해, 구간 $(i, j)$ 내 최댓값을 가지는 유일한 위치 $k$가 존재한다. 이 $k$를 기준으로 좌우에서 가장 가까운 $A_k$보다 큰 값을 찾는다:

• $\text{left}[k]$: $k$ 왼쪽에서 $A_k$보다 큰 첫 번째 인덱스
• $\text{right}[k]$: $k$ 오른쪽에서 $A_k$보다 큰 첫 번째 인덱스

이 값들은 단조 스택을 사용해 $O(N)$ 시간에 전처리할 수 있다.

각 $k$에 대해 가능한 $(i, j)$ 쌍은 다음과 같이 세 가지 유형으로 나뉜다:

1. $(\text{left}[k], k)$: 이때 $j = k$, $i = \text{left}[k]$, 그리고 $k+1$부터 $\text{right}[k]-1$ 사이의 모든 $j'$에 대해 $(i, j')$는 조건 2를 만족 → $p_2$ 기여
2. $(k, \text{right}[k])$: 유사하게, $\text{left}[k]+1$부터 $k-1$ 사이의 모든 $i'$에 대해 $(i', j)$는 조건 2를 만족 → $p_2$ 기여
3. $(\text{left}[k], \text{right}[k])$: 이 쌍은 조건 1을 만족 → $p_1$ 기여

이제 각 질의 $[l, r]$에 대해, 위 세 가지 유형의 기여를 효율적으로 계산해야 한다.

오프라인 처리: 스위핑 + 세그먼트 트리

각 기여를 "위치 $pos$가 질의 범위에 포함되면, 구간 $[L, R]$에 $val$을 더한다"는 형태의 갱신 연산으로 변환한다.

질의는 다음과 같이 분해된다:

• $[1, r]$까지의 누적 기여에서 $[1, l-1]$까지의 누적 기여를 뺀 값

이를 위해:

1. 모든 갱신 연산을 $pos$ 기준으로 정렬
2. 질의도 $pos$ 기준으로 정렬 후 스위핑
3. 세그먼트 트리를 이용해 구간 갱신과 구간 합 쿼리를 처리

세그먼트 트리는 지연 전파 없이, 각 노드에 전체 구간에 대한 델타($tot$)와 부분 구간 합($sum$)을 저장하는 방식으로 구현된다.

온라인 처리: 퍼시스턴트 세그먼트 트리

각 위치 $i$에 대해, $pos \le i$인 모든 갱신을 적용한 세그먼트 트리 $rt[i]$를 유지한다.

질의 $[l, r]$에 대한 답은:

qry(rt[r], rt[l-1], 1, n, l, r) + (r - l) * p1

여기서 $qry(rt_a, rt_b, ...)$는 두 버전 간의 차이를 이용해 구간 합을 계산한다.

이 구현은 메모리와 시간이 더 소모되지만, 질의를 즉시 처리할 수 있다는 장점이 있다.

코드 요약

두 접근 모두 다음 단계를 공유한다:

1. 단조 스택으로 $\text{left}[k]$, $\text{right}[k]$ 전처리
2. 각 $k$에 대해 세 가지 기여 유형을 갱신 연산으로 변환
3. 오프라인: 스위핑 + 일반 세그먼트 트리
   온라인: 퍼시스턴트 세그먼트 트리
4. 인접 쌍 기여 $(r - l) \cdot p_1$을 별도로 추가

아래는 오프라인 풀이의 핵심 로직을 재구성한 의사코드이다:

// 전처리
for i = 1 to n:
    while stack not empty and A[stack.top] < A[i]: pop
    left[i] = stack.empty ? 0 : stack.top
    push i

clear stack
for i = n downto 1:
    while stack not empty and A[stack.top] < A[i]: pop
    right[i] = stack.empty ? n+1 : stack.top
    push i

// 갱신 생성
events = []
for k = 1 to n:
    if left[k] != 0 and k+1 <= right[k]-1:
        events.append( (left[k], k+1, right[k]-1, p2) )
    if right[k] <= n and left[k]+1 <= k-1:
        events.append( (right[k], left[k]+1, k-1, p2) )
    if left[k] != 0 and right[k] <= n:
        events.append( (right[k], left[k], left[k], p1) )

sort events by pos

// 질의 변환 및 정렬
queries = []
for each query [l, r]:
    ans_base = (r - l) * p1
    queries.append( (l-1, -1, id, l, r) )
    queries.append( (r,   +1, id, l, r) )

sort queries by pos

// 스위핑
nw = 1
for each q in queries:
    while nw <= len(events) and events[nw].pos <= q.pos:
        seg.update(events[nw].L, events[nw].R, events[nw].val)
        nw++
    ans[q.id] += q.sign * seg.query(q.L, q.R)

// 출력 ans[id] + ans_base