백준19088 Biggest Number

작성일 | In

문제 링크

  • http://icpc.me/19088

사용 알고리즘

  • 세그먼트 트리

시간복잡도

  • $O(Q log N)$

풀이

현재 갖고 있는 수들로 만들 수 있는 가장 큰 수는 현재 갖고 있는 수를 내림차순한 결과입니다.

세그먼트 트리의 i번째 리프노드에 현재 갖고 있는 i의 개수를 저장합니다. 만약 5를 3개 갖고 있다면 555, 4개 갖고 있다면 5555처럼 표현해야 합니다. 이를 편하게 하기 위해서 다음과 같은 배열을 정의합시다.

  • one[i] = D진법 상에서 1이 i개 있는 수를 1e9+7로 나눈 나머지

이런 배열을 알고 있으면 a가 b개 있는 수를 a × one[b] mod 1e9+7로 구할 수 있습니다.

리프노드는 쉽게 표현 가능하지만, 두 자식 정점의 값을 합쳐서 부모 정점을 만드는 것은 조금 복잡해 보입니다. 부모 정점의 값은 양쪽 자식에 숫자가 몇 개 있는지 있는지, 양쪽 자식이 어떤 수를 표현하는지에 따라 달라지게 됩니다.
왼쪽 자식 정점 L과 오른쪽 자식 정점 R을 합쳐서 부모 정점 P를 만드는 방법을 알아봅시다.

가장 큰 수를 만들기 위해서는 큰 숫자가 앞에 나와야 합니다. 그리고 큰 숫자는 오른쪽 자식에 있습니다. 그러므로 P가 표현하는 값은 R이 표현하는 값 뒤에 L이 표현하는 값이 따라오는 형태가 됩니다. R이 표현하는 값 뒤에 0을 적당히 붙인 뒤 L이 표현하는 값을 더하면 되므로, 아래 배열을 미리 구해놓읍시다.

  • pw[i] = $D^i \mod 1e9+7$

왼쪽 정점에 있는 숫자의 개수를 ls, 오른쪽 정점에 있는 숫자의 개수를 rs, 왼쪽 정점이 표현하는 수를 lv, 오른쪽 정점이 표현하는 수를 rv라고 한다면, P가 표현하는 수는 아래와 같이 계산할 수 있습니다.
rv × pw[ls] + lv

위 식은 rv 위에 lv의 길이만큼 0을 붙이고 lv를 더한 값을 의미합니다.

세그먼트 트리를 갱신해주면서 값을 잘 관리해주면 됩니다.
수의 범위가 최대 10억인데, 동적 세그먼트 트리를 만들거나 좌표 압축을 해주면 메모리를 아낄 수 있습니다.

전체 코드

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
69
70
71
72
73
74
75
76
77
78
79
80
#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;
const ll mod = 1e9+7;

ll pw[202020], one[202020];

struct Node{
	int l, r;
	ll sz, val;
	Node() : l(-1), r(-1), sz(0), val(0) {}
	Node operator + (const Node &t) const {
		Node ret;
		ret.sz = sz + t.sz;
		ret.val = t.val * pw[sz] % mod + val; ret.val %= mod;
		return ret;
	}
};

vector<Node> tree;

void update(int node, int s, int e, int x, int v){
	if(s == e){
		tree[node].sz += v;
		tree[node].val = one[tree[node].sz] * x % mod;
		return;
	}
	int m = s + e >> 1;
	if(x <= m){
		if(tree[node].l == -1) tree[node].l = tree.size(), tree.emplace_back();
		update(tree[node].l, s, m, x, v);
	}
	else{
		if(tree[node].r == -1) tree[node].r = tree.size(), tree.emplace_back();
		update(tree[node].r, m+1, e, x, v);
	}
	ll ls = 0, rs = 0, lv = 0, rv = 0;
	if(tree[node].l != -1){
		ls = tree[tree[node].l].sz;
		lv = tree[tree[node].l].val;
	}
	if(tree[node].r != -1){
		rs = tree[tree[node].r].sz;
		rv = tree[tree[node].r].val;
	}
	tree[node].sz = ls + rs;
	tree[node].val = rv * pw[ls] + lv; tree[node].val %= mod;
}
int query(){ return tree[0].val; }

int n, q, d;
int val[101010];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> q >> d; tree.emplace_back();
    pw[0] = one[1] = 1;
    for(int i=1; i<202020; i++){
    	pw[i] = pw[i-1] * d % mod;
    }
    for(int i=2; i<202020; i++){
    	one[i] = (one[i-1] + pw[i-1]) % mod;
    }
    for(int i=1; i<=n; i++){
    	cin >> val[i]; update(0, 0, d-1, val[i], 1);
    }
	cout << query() << "\n";
    while(q--){
    	int a, b; cin >> a >> b;
    	update(0, 0, d-1, val[a], -1);
    	val[a] = b;
    	update(0, 0, d-1, val[a], 1);
    	cout << query() << "\n";
    }
}