세그먼트 트리의 구간 갱신을 빠르게 처리하기 위한 방법으로, 별도의 배열을 사용하여 필요한 만큼만 부분적으로 세그먼트 트리의 값을 갱신하여 시간복잡도를 줄일 수 있습니다.
구현
기준 문제 : https://www.acmicpc.net/problem/2934
2934번: LRH 식물
상근이는 유전자 조작을 통해 줄기 두 개로 이루어진 식물을 만들었다. 이 식물은 줄기의 x좌표 L, R과 높이 H로 나타낼 수 있다. 아래 그림은 L=2, R=5, H=4인 식물이다. 상근이는 매일 매일 화단에
www.acmicpc.net
|
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
|
#import <stdio.h>
#import <algorithm>
#define NMAX 100010
typedef long long int lint;
using namespace std;
int N, L, R, ed;
int inp[NMAX][2];
lint lt, rt, ret;
lint segTree[NMAX*4], lazy[NMAX*4];
void updateLazy(int idx, int il, int ir) {
segTree[idx] += lazy[idx];
if(il != ir) {
lazy[idx*2] += lazy[idx];
lazy[idx*2+1] += lazy[idx];
}
lazy[idx] = 0;
}
lint search(int idx, int il, int ir, int ql, int qr) {
if(lazy[idx]) updateLazy(idx, il, ir);
if(il>qr or ir<ql) return 0;
else if(ql<=il and ir<=qr) return segTree[idx];
else {
int mid = (il+ir)/2;
return max( search(idx*2, il, mid, ql, qr), search(idx*2+1, mid+1, ir, ql, qr) );
}
}
void update(int idx, int il, int ir, int ql, int qr, lint val) {
if(lazy[idx]) updateLazy(idx, il, ir);
if(il>qr or ir<ql) return;
else if(ql<=il and ir<=qr) {
lazy[idx] += val;
updateLazy(idx, il, ir);
}
else {
int mid = (il+ir)/2;
update(idx*2, il, mid, ql, qr, val);
update(idx*2+1, mid+1, ir, ql, qr, val);
segTree[idx] = max( segTree[idx*2], segTree[idx*2+1] );
}
}
int main() {
scanf("%d", &N);
for(int i=1;i<=N;i++) {
scanf("%d %d", &inp[i][0], &inp[i][1]);
ed = max( ed, inp[i][1] );
}
for(int i=1;i<=N;i++) {
L = inp[i][0]; R = inp[i][1];
lt = search(1, 1, ed, L, L);
rt = search(1, 1, ed, R, R);
ret = lt + rt;
if(lt>0) update(1, 1, ed, L, L, -lt);
if(rt>0) update(1, 1, ed, R, R, -rt);
if(R-L > 1) update(1, 1, ed, L+1, R-1, 1);
printf("%lld\n", ret);
}
}
|
cs |