[ABC038 C] 単調増加

난이도: 894 // 실험적

 

번역

\( N \)개의 정수가 주어집니다. \( i \)번째 수는 \( a_{i} \)입니다.

\( l \le r \)이면서 \( a_{l}, a_{l+1}, \ldots, a_{r} \)이 증가수열이 되도록 하는 \( (l, r) \)의 개수를 찾으세요.

즉, \( l \le i < r \)인 모든 \( i \)에 대해 \( a_{i} < a_{i+1} \)를 만족시키는 \( (l, r) \)의 개수를 찾으세요.

 

태그

• Sweeping (스위핑)

 

풀이

1. \( l \)을 고정시킬 때, 가능한 개수는?

조건의 특성상, \( r_1 < r_2 \)이고 \( (l, r_2) \)가 증가수열이었다면, \( (l, r_1) \)도 증가수열이 됩니다.

또한, \( r_1 < r_2 \)이고 \( (l, r_1) \)이 증가수열이 아니라면, \( (l, r_2) \)도 증가수열이 아니게 됩니다.

 

이제, \( r \)을 \( l \)에서부터 시작해서 오른쪽으로 한 칸씩 이동해봅시다.

그럼, \( r \)은 \( a_{r} \ge a_{r+1} \)을 만나게 되거나, \( N \)번째 수까지 이동하게 됩니다.

 

\( r \)이 멈추게 되면, 어떤 특정한 \( l \)에 대해 증가수열을 만들게 되는 \( r \)의 끝점을 알게 되고,

시작점은 자명히 \( r = l \)일테니, 가능한 경우는 \( r-l+1 \)가지가 됨을 알 수 있습니다.

 

2. 더 빠르게 구해보기

(1번)의 방식대로만 돌리면, \( O(N^2) \)의 시간이 나오게 됩니다.

하지만, \( l \)을 \( N \)부터 한 칸씩 왼쪽으로 이동시키면, 이로 인한 \( r \)의 위치는 아래 둘 중 하나로 고정됩니다.

• \( a_{l} < a_{l+1} \): \( r \)의 위치에 변함이 없습니다. \( a_{l} < a_{l+1} \) 다음의 비교는 \( l+1 \)에서 한 비교와 동일할테니까요.
• \( a_{l} \ge a_{l+1} \): \( r \)의 끝점이 \( l \)로 이동합니다. 첫 비교부터 증가수열이 아니라는 결론이 나왔으니까요.

 

다르게 말하자면, \( l \)을 \( N \)에서부터 왼쪽으로 이동시키면, 새로운 \( r \)의 위치를 \( O(1) \)에 계산할 수 있게 됩니다.

 

코드

int arr[100020];
 
void Main(){
    int n; cin >> n;
    for (int i = 1; i <= n; i++){ cin >> arr[i]; }
    ll ans = 0;
    int lst = n; for (int i = n; i >= 1; i--){
        if (arr[i] >= arr[i+1]){ lst = i; }
        ans += lst-i+1;
    }
    cout << ans;
}