반응형

https://www.acmicpc.net/problem/1395

 

1395번: 스위치

첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/256

 

[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)

https://rudalsd.tistory.com/51 [ 자료구조 ] 세그먼트 트리 (Segment Tree) 1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다.

rudalsd.tistory.com

 

1. 세그먼트 트리와 lazy값을 저장할 배열을 만듭니다.

 

2. 해당 노드에서 스위치를 두 번 작동시키면 원상복구 되므로, lazy 배열을 -1 또는 1로 갱신합니다.

 

3. 해당 노드에서 스위치가 작동되면 전구의 수가 총 개수 - 현재 켜져있는 전구의 수로 바뀌므로 e - s + 1 - segTree[node]를 이용하여 갱신해줍니다.

 

4. 느리게 갱신되는 세그먼트 트리를 활용하여 Update를 하고 구간 합을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int segTree[262222];
int lazy[262222];
int N, M;
 
void modifyLazy(int node, int s, int e)
{
    if (lazy[node] == 1) {
        segTree[node] = e - s + 1 - segTree[node];
        if (s != e) {
            lazy[node * 2] *= -1;
            lazy[node * 2 + 1] *= -1;
        }
        lazy[node] *= -1;
    }
}
 
void modifyTree(int node, int s, int e, int sidx, int eidx)
{
    modifyLazy(node, s, e);
 
    if (eidx < s || e < sidx) return;
 
    if (sidx <= s && e <= eidx) {
        segTree[node] = e - s + 1 - segTree[node];
        if (s != e) {
            lazy[node * 2] *= -1;
            lazy[node * 2 + 1] *= -1;
        }
        return;
    }
 
    int m = (s + e) / 2;
    modifyTree(node * 2, s, m, sidx, eidx);
    modifyTree(node * 2 + 1, m + 1, e, sidx, eidx);
 
    segTree[node] = segTree[node * 2] + segTree[node * 2 + 1];
}
 
int getTree(int node, int s, int e, int sidx, int eidx)
{
    modifyLazy(node, s, e);
 
    if (eidx < s || e < sidx) return 0;
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
    return getTree(node * 2, s, m, sidx, eidx) + getTree(node * 2 + 1, m + 1, e, sidx, eidx);
}
 
int main()
{
    fill(lazy, lazy + 262222, -1);
 
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < M; i++) {
        int O, S, T;
 
        scanf("%d %d %d", &O, &S, &T);
 
        if (S > T) swap(S, T);
 
        if (O == 0) {
            modifyTree(1, 1, N, S, T);
        }
        else {
            printf("%d\n", getTree(1, 1, N, S, T));
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 12844번 - XOR (C++)  (0) 2023.05.06
[ 백준 ] 11003번 - 최솟값 찾기 (C++)  (0) 2023.05.05
[ 백준 ] 9426번 - 중앙값 측정 (C++)  (0) 2023.05.02
[ 백준 ] 1572번 - 중앙값 (C++)  (0) 2023.05.01
[ 백준 ] 4195번 - 친구 네트워크 (C++)  (0) 2023.04.30

+ Recent posts

티스토리툴바