백준16791 Bubble Sort 2

작성일 | In

문제 링크

  • http://icpc.me/16791

문제 출처

  • JOIOC 2018 1번

사용 알고리즘

  • Segment Tree
  • Lazy Propagation

시간복잡도

  • $O((N+Q) \log N)$

풀이

Subtask 2 (38점)

집합 $S_i$를 $A_i$보다 앞에 있으면서 더 큰 수들의 집합($j < i ∧ A_j > A_i$)으로 정의합시다.

$S_i$의 크기가 0보다 크다면, $A_i$는 한 번의 pass를 통해 한 칸 앞으로 이동합니다. $S_i$의 크기가 0이라면 $A_i$는 적절히 뒤로 이동합니다. 그러므로 문제의 정답은 $\max(\vert S_i \vert)$입니다.
좌표압축을 한 뒤, 각 쿼리를 Fenwick Tree를 이용해 $O(N \log N)$에 처리해주면 총 $O(NQ \log N)$으로 38점을 받을 수 있습니다.

Full Solution (100점)

점 $(i, A_i)$를 좌표 평면에 찍어보면, Convex Hull의 오른쪽 아래에 있는 점만 정답($\vert S_i \vert$의 최댓값)이 될 수 있습니다. 그리고 이런 점에 대해서는 $\vert S_i \vert = i - $ ($A_i$보다 작은 원소의 개수)가 만족합니다.
나머지 점들에 대해서는 $\vert S_i \vert > i - $ ($A_i$보다 작은 원소의 개수) $\geq i - $ ($A_i$보다 작거나 같은 원소의 개수)입니다.

그러므로 쿼리가 주어질 때마다 $\vert S_i \vert$대신 ($i - $ ($A_i$보다 작은 원소의 개수))를 관리해도 충분합니다.
$i$는 상수이므로 ($A_i$보다 작은 원소의 개수)만 잘 관리해주면 됩니다.

배열에서 어떤 수 $x$가 빠지면 $x$보다 큰 $A_i$에 대해서, $A_i$보다 작은 원소의 개수가 1 증가합니다.
배열에 어떤 수 $x$가 추가되면 $x$보다 큰 $A_i$에 대해서, $A_i$보다 작은 원소의 개수가 1 감소합니다.

$A_x$를 $v$로 바꾸는 쿼리는 배열에서 $A_x$를 삭제하고 $v$를 추가하는 것으로 생각할 수 있고, 각 연산은 임의의 구간에 1을 더하거나 빼는 것으로 생각할 수 있습니다.
그러므로 Segment Tree와 Lazy Propagation을 사용해서 $O((N+Q) \log N)$에 문제를 해결할 수 있습니다.

전체 코드

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
#include "bubblesort2.h"
#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())
using namespace std;

typedef long long ll;
typedef pair<int, int> p;
const int inf = 1e9;

int tree[1 << 21], tmp[1 << 21];
const int sz = 1 << 20;
void push(int node, int s, int e){
    if(!tmp[node]) return;
    tree[node] += tmp[node];
    if(s != e){
        tmp[node << 1] += tmp[node];
        tmp[node << 1 | 1] += tmp[node];
    }
    tmp[node] = 0;
}
void update(int node, int s, int e, int l, int r, int v){
    push(node, s, e);
    if(r < s || e < l) return;
    if(l <= s && e <= r){ tmp[node] += v; push(node, s, e); return; }
    int m = s + e >> 1;
    update(node << 1, s, m, l, r, v);
    update(node << 1 | 1, m+1, e, l, r, v);
    tree[node] = max(tree[node << 1], tree[node << 1 | 1]);
}
int query(int node, int s, int e, int l, int r){
    push(node, s, e);
    if(r < s || e < l) return 0;
    if(l <= s && e <= r) return tree[node];
    int m = s + e >> 1;
    return query(node << 1, s, m, l, r) + query(node << 1 | 1, m+1, e, l, r);
}
void update(int s, int e, int x){ update(1, 0, sz-1, s, e, x); }
int query(int s, int e){ return query(1, 0, sz-1, s, e); }

void insert(int x, int v){ update(v, v, inf+x); update(v+1, sz-1, -1); }
void erase(int x, int v){ update(v, v, -inf-x); update(v+1, sz-1, 1); }

vector<int> count_scans(vector<int> a, vector<int> x, vector<int> v){
    int n = a.size(), q = x.size();
    vector<p> comp; update(0, sz-1, -inf);

    for(int i=0; i<n; i++) comp.emplace_back(a[i], i);
    for(int i=0; i<q; i++) comp.emplace_back(v[i], x[i]);
    compress(comp);
    for(int i=0; i<n; i++) a[i] = lower_bound(all(comp), p(a[i], i)) - comp.begin();
    for(int i=0; i<q; i++) v[i] = lower_bound(all(comp), p(v[i], x[i])) - comp.begin();

    vector<int> ret;
    for(int i=0; i<n; i++) insert(i, a[i]);
    for(int i=0; i<q; i++){
        erase(x[i], a[x[i]]);
        insert(x[i], a[x[i]] = v[i]);
        ret.push_back(query(0, sz-1));
    }
    return ret;
}