ABC441 - E - A > B substring (작성중)

Problem

길이 $N$인 문자열 $S$가 주어집니다. $S$는 ‘A’, ‘B’, ‘C’ 세 종류의 문자로만 구성되어 있습니다. $S$의 모든 가능한 연속된 부분 문자열 $\frac{N(N+1)}{2}$개 중에서, ‘A’의 개수가 ‘B’의 개수보다 엄격히 많은(strictly more) 부분 문자열의 총 개수를 구하는 프로그램을 작성하세요.

• $1 \le N \le 5 \times 10^5$
• 시간 제한: 2초
• 메모리 제한: 1024 MiB

Complexity Analysis

시간복잡도 : O(Nlogn) 또는 O(N) 이어야 함

Approach

초기 접근

• 우리가 찾는 조건은 A개수 > B개수 이다.
• 이항하면 A개수 - B개수 > 0
• 가중치를 부여한다.
  • A : +1
  • B : -1
  • C : 0 (가중치 영향 x)
• 이렇게 가중치를 두면, 어떤 구간 $[i, j]$의 구간 합(Sum of Subarray)이 0보다 크면 그 구간은 A가 B보다 많은 구간이 됩니다.

정리

이러면 문제가 바뀌게 되는데

$P_j - P_{i-1} > 0$, 즉 $P_j > P_{i-1}$을 만족하는 쌍 $(i-1, j)$의 개수를 구하라

단, $0 \le i-1 < j \le N$

이 문제는 정렬되지 않은 배열 $P$에서 “자신보다 앞에 있으면서 값이 더 작은 원소의 개수”를 세는 문제가 되었습니다.

단순히 $i$와 $j$를 모두 대입해보는 이중 루프는 정확히 $O(N^2)$이며, 우리가 피하고자 하는 방식이다.

$j$를 $0$부터 $N$까지 순차적으로 확인하면서, “지금까지 지나온 $P_i$ 값들 중 현재 $P_j$보다 작은 값이 몇 개나 있었지?”를 빠르게 물어볼 수 있다면

solve