[ABC038 C] 単調増加

난이도: 894 // 실험적

 

번역

$N$개의 정수가 주어집니다. $i$번째 수는 $a_i$입니다.

$l\le r$이면서 $a_l,a_{l+1},\dots ,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;
}