2855 흥미로운 수열

구간합을 사용해서 이분탐색을 해도 되고 누적합을 사용해서 해당 위치에서 좌우로 얼마나 뻗을 수 있는지를 구해도 된다.

나는 이분탐색을 사용했다.

i : 0~n까지 차례대로 이분탐색을 한다.

i를 중심으로 좌우로 최대 얼마나 뻗을 수 있는지 이분탐색을 한 후

그 결과를 map에 저장한다(중요).

중요한 조건이 하나 있는데

--------------------------------------------------------------

i를 중심으로 좌우로 최대 mid만큼이 흥미로운 수열일 때

i를 중심으로 0~mid까지 모두 흥미로운 수열을 만족한다.

--------------------------------------------------------------

하지만 이걸 일일이 업데이트 시켜주면 시간초과가 난다.

그러므로 map에 {시작위치, 반지름} 형태로 저장시키고 만약 시작위치가 같다면 업데이트만 시켜주면 된다.

이렇게 하면 map에 듬성듬성 데이터가 들어가게 되는데

위에서 말했던 조건을 적절히 적용해야 한다.

간단한 예로

7 9

1

1

1

1

10

1

9

를 입력하면 map에

(0,2) (2,1) (5,1)이 들어가있다.

이걸로 결과를 일단 만들어 보면

4

0

2

0

0

2

0

이 나온다. 그리고 시작위치 0~2 사이에 1의 데이터가 비어있는데 조건에 따르면 0에서 반지름 2짜리 흥미로운 수열이 성립하므로

1에서는 [이전 위치에서 성립하는 흥미로운 수열의 반지름] - 1짜리는 무조건 성립하게 된다. 나머지 구간도 마찬가지로 적용할 수 있지만

흥미로운 수열의 길이가 -가 될 수는 없으므로 달라지는 것은 없다. 따라서

4

2

2

0

0

2

0

라는 결과가 나온다.

#include <stdio.h>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
 
int n, s, a[100001];
map<int, int> m;
 
void bis(int pivot) {
    int l = 0, r = min(n - pivot, pivot), mid = (l + r) / 2, ans = 0;
    while (l <= r) {
        mid = (l + r) / 2;
        int sl = a[pivot] - a[pivot - mid];
        int sr = a[pivot + mid] - a[pivot];
        if (sl > s || sr > s) r = mid - 1;
        else {
            ans = mid;
            l = mid + 1;
        }
    }
    if (!ans) return;
    if (m.count(pivot - ans)) 
        m[pivot - ans] = max(m[pivot - ans], ans);
    else 
        m.insert({ pivot - ans, ans });
}
 
int main() {
    scanf("%d%d", &n, &s);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        a[i] += a[i - 1];
    }
    for (int i = 1; i < n; i++) 
        bis(i);
    int prev = 0;
    auto it = m.begin();
    for (int i = 0; i < n; i++) {
        if (it == m.end()) {
            printf("%d\n", max(--prev, 0) * 2);
            continue;
        }
        prev = max(prev - 1, 0);
        if (i == (*it).first) 
            prev = max(prev, (*it++).second);
        printf("%d\n", prev * 2);
    }
    return 0;
}