백준18944 Non-Decreasing Subarray Game

작성일 | In

문제 링크

  • http://icpc.me/18944

사용 알고리즘

  • 파라메트릭 서치
  • 누적합

시간복잡도

  • $O(N \log N)$

풀이

구간 $[s, e]$의 Non Decreasing Subarray의 개수를 $C(s, e)$로 정의합시다.

Platina는 $L$ 또는 $R$을 부를 것이고, Yuto는 $\max(C(L, t), C(t, R))$이 최소가 되는 $t$를 부를 것입니다.
$L, R$이 고정되어 있을 때 어떤 지점까지는 $C(L, t) \leq C(t, R)$이고, 그 다음 지점부터는 $C(L, t) < C(t, R)$입니다. $\max(C(L, t), C(t, R))$가 최소가 되기 위해서는 $C(L, t)$와 $C(t, R)$의 대소 관계가 바뀌는 경계를 선택해야 합니다.

만약 $C(s, e)$를 $T(N)$ 시간에 구할 수 있다면 대소 관계가 바뀌는 경계는 파라메트릭 서치를 이용해 $T(N) \log N$에 구할 수 있습니다. $C(s, e)$를 $O(1)$에 구하는 방법을 알아봅시다.

연속한 $X$개의 원소가 감소하지 않는 수열이라면, 그 구간에서의 Non Decreasing Subarray의 개수는 $\frac{X(X+1)}{2}$입니다. 해당 구간의 시작 지점에 $\frac{X(X+1)}{2}$를 더하고 누적합을 구해주면 $O(N)$만에 전처리를 할 수 있습니다.
$C(s, e)$의 값을 구하는 것은 위에서 만든 누적합 배열을 활용해서 $O(1)$만에 구해줄 수 있습니다. 구현이 까다로울 수 있는데, 아래 3가지 경우에 대해 각각 코딩해주면 됩니다.

  1. 연속한 ‘감소하지 않는 수열’의 오른쪽 일부가 구간 $[s, e]$에 포함되는 경우
  2. 연속한 ‘감소하지 않는 수열’이 모두 구간 $[s, e]$에 포함되는 경우
  3. 연속한 ‘감소하지 않는 수열’의 왼쪽 일부가 구간 $[s, e]$에 포함되는 경우

2번째 케이스는 누적합을 이용해 $O(1)$만에 처리할 수 있고, 1, 3번째 케이스는 한 번 밖에 나오지 않기 때문에 적절히 구현해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define int long long
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

int n, q, g[505050];
ll a[505050], sum[505050];
vector<p> v;

ll f(int s, int e){
    if(s > e) return 0;
    ll res = sum[e] - sum[s-1], t;
    int flag = 0;
    if(g[s-1] == g[s]){
        flag = 1;
        t = min(v[g[s]].y, e) - s + 1;
        res += t * (t + 1) / 2;
    }
    if(g[e] == g[e+1]){
        if(g[s] == g[e] && flag) return res;
        t = v[g[e]].y - v[g[e]].x + 1;
        res -= t * (t + 1) / 2;
        t = e - v[g[e]].x + 1;
        res += t * (t + 1) / 2;
    }
    return res;
}

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> q; for(int i=1; i<=n; i++) cin >> a[i];
    int st = 1;
    for(int i=2; i<=n+1; i++){
        if(a[i-1] > a[i]) v.emplace_back(st, i-1), st = i;
    }
    int pv = 0;
    g[0] = -1; g[n+1] = n+1;
    for(auto i : v){
        for(int j=i.x; j<=i.y; j++) g[j] = pv; pv++;
        ll t = i.y - i.x + 1;
        t = t * (t + 1) / 2;
        sum[i.x] += t;
    }
    for(int i=1; i<505050; i++) sum[i] += sum[i-1];

    while(q--){
        int s, e; cin >> s >> e;
        int l = s, r = e;
        while(l < r){
            int m = l + r + 1 >> 1;
            ll t1 = f(s, m), t2 = f(m, e);
            if(t1 < t2) l = m;
            else r = m - 1;
        }
        ll res = max(f(s, l), f(l, e));
        for(int i=-2; i<=2; i++){
            if(l+i < s || e < l+i) continue;
            res = min(res, max(f(s, l+i), f(l+i, e)));
        }
        cout << res << "\n";
    }
}