백준 15670, 도로 공사

개요

문제 링크
골드 2, 누적합
구간 L,R을 뒤집었을 때 증가하는 연속부분수열 개수 구하기

---

접근

1. 먼저 N을 보자. 10만이니까 O(NlogN)이상은 사용할 수 없다. 아하 O(N)안에 끝내라는 말이구나.

2. O(N)안에 끝내는 가장 좋은 방법은 연산에 필요한 데이터를 만들어두고, O(1)안에 연산을 마치는 것이다. 보통 이런 유형의 문제에 누적합을 사용한다.

3. 누적합을 어떻게 사용하냐? 하면 우선 문제를 풀 방법부터 생각해보자.

   1. 배열을 직접 뒤집어서 매번 오르막을 세어주는 것이 가장 쉽게 생각할 수 있는 방법이고 가장 오래걸린다. 뒤집는데 O(N), 세어주는데 O(N)이 걸리니까 O(MN)으로 1e10번 연산이 필요하다. 시간초과.
   2. 그럼 (L,R)에 대한 오르막과 내리막을 전부 저장한 뒤, (1,L-1)의 오르막+(R+1,N)의 오르막+(L,R)의 내리막을 계산해준다면? O(1)에 연산을 할 수는 있겠지만 N×N의 배열이 필요해서 메모리 초과가 날 것이다.
   3. 그럼 연산방법은 2번의 방법을 유지하고, 1차원 배열을 이용하는 방법을 생각하면? 이때 누적합을 사용한다. i까지의 오르막, 내리막 개수를 저장하는 1차원 배열 두 개를 생성한뒤, (i,j)의 오르막 개수는 a[j]-a[i-1]로 계산해준다.

4. 이때 추가적으로 고민할 부분이 두 가지가 있는데,

   1. 만약 뒤집은 배열이 양 끝 구간의 오르막에 포함된다면? 이때는 오르막 개수를 1개씩 빼주어야 한다. 조건은 아래와 같다.

       a[r]>a[l-1] // 오른쪽 끝이 왼쪽 오르막에 포함 
       a[l]<a[r+1] // 왼쪽 끝이 오른쪽 오르막에 포함

   2. 여기까지는 그럭저럭 쉽게 생각해볼 수 있지만, 누적합을 사용하면서 문제가 엄청 헷갈려진다. 아래 예시를 보자.

       1 2 4 3 5
       (l,r)=(3,4)
       -> 1 2 3 4 5
       // answer=1
      
       up[l-1] = up[2] = 1 // 1
       up[n] = 2, up[r] = 2 // 0
       down[l-1] = 2, down[r] = 3 // 1
      
       output = up[l-1]+(up[n]-up[r])+(down[r]-down[l-1]) = 2
       // a[r]>a[l-1], output--
       // a[l]<a[r-1], output--
       output = 0

      엥 하는 결과가 나와버렸다. 그럼 a[r]>a[l-1]을 고려하지 말아야 할까? 하면 그건 아니다. 뒤집었을 때 양 옆 오르막에 추가된다는 사실은 직관적으로도 생각할 수 있는 사실이기 때문이다.

   3. 그럼 어떻게 하냐 하면, 위 예시의 문제는 up[n]-up[r]와 down[r]-down[l-1]을 하는 과정에서 생긴다. 만약 r과 r+1이 같은 오르막에 속해있다면? 오른쪽 덩이를 분리하는 과정에서 첫 원소 (r+1) 가 오르막의 시작으로 인식되지 않는다. 마찬가지로 l-1과 l이 같은 내리막에 속해있다면 l-1이 내리막의 시작으로 인식되지 않는다. 즉

       up[r]==up[r+1]
       down[l]==down[l-1]

      을 만족할 때 결과값에 1을 추가하면 된다. 이 말이 엄청 헷갈릴 수 있는데 오르막의 시작으로 인식된다 라는 생각을 잘 해보면 이해할 수 있을 것이다.

---

Pseudo code

up = 오르막개수
dn = 내리막개수
up[1]=1, dn[1]= 1

for (i: a)
    if (a[i]>a[i-1]) dn[i]++
    else up[i]++
for (m)
    LU = up[l-1]
    RU = up[n]-up[r]
    LRD = dn[r]-dn[l-1]
    if (up[r]==up[r+1]) RU++
    if (dn[l]==dn[l-1]) LRD++

    cnt=LU+RU+LRD
    if (a[r]>a[l-1]) cnt--
    if (a[l]<a[r+1]) cnt--
    print(cnt)

---

Source code

// 3196KB, 44ms
#include <bits/stdc++.h>
using namespace std;

using vec=vector<int>;

int main() {
    cin.tie(0);ios::sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    vec a(n+2),up(n+2,0),dn(n+2,0);
    a[0]=2e9,a[n+1]=0;
    cin>>a[1],up[1]=dn[1]=1;
    for (int i=2;i<=n;i++) {
        cin>>a[i];
        up[i]=up[i-1],dn[i]=dn[i-1];
        if (a[i]>a[i-1]) dn[i]++;
        else up[i]++;
    }
    while (m--) {
        int l,r,v;
        cin>>l>>r;
        v=up[l-1]+up[n]-up[r];
        v+=dn[r]-dn[l-1];
        if (up[r]==up[r+1]) v++;
        if (dn[l]==dn[l-1]) v++;
        if (a[r]>a[l-1]) v--;
        if (a[l]<a[r+1]) v--;
        cout<<v<<"\n";
    }
}

// 2288KB, 72ms
#include <stdio.h>

#define N 100010
int a[N],up[N],dn[N];

int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    a[0]=2e9;
    scanf("%d",a+1),up[1]=dn[1]=1;
    for (int i=2;i<=n;i++) {
        scanf("%d",a+i);
        up[i]=up[i-1],dn[i]=dn[i-1];
        if (a[i]>a[i-1]) dn[i]++;
        else up[i]++;
    }
    while (m--) {
        int l,r,v;
        scanf("%d%d",&l,&r);
        v=up[l-1]+up[n]-up[r];
        v+=dn[r]-dn[l-1];
        if (up[r]==up[r+1]) v++;
        if (dn[l]==dn[l-1]) v++;
        if (a[r]>a[l-1]) v--;
        if (a[l]<a[r+1]) v--;
        printf("%d\n",v);
    }
}

# 135120KB, 380ms
import sys;input=sys.stdin.readline
def inp():return list(map(int,input().split()))
n,m=inp();a=[2e9]+inp()+[0]

up=[0]*(n+2);dn=[0]*(n+2)
up[1]=1;dn[1]=1

for i in range(2,n+1):
    up[i],dn[i]=up[i-1],dn[i-1]
    if (a[i]>a[i-1]): dn[i]+=1
    else: up[i]+=1

for i in range(m):
    l,r=inp()
    v=up[l-1]+up[n]-up[r]
    v+=dn[r]-dn[l-1]
    if up[r]==up[r+1]:v+=1
    if dn[l]==dn[l-1]:v+=1
    if a[r]>a[l-1]:v-=1
    if a[l]<a[r+1]:v-=1
    print(v)