BOJ1395: 스위치

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

  • Bottom-up Lazy Propagation 방식에 대한 쓸데업는 집착을 버렸다.
  • Bottom-up은 Point Query일때만 쓰자.. ㅠㅠ
  • Top-down으로 하면 코드도 훨신 명쾌하고 간단해진다.
  • 먼저 Update 할때
    • ValProp을 값을 다시 계산해주고, Propagation 하는 것이라고 하자.
    • Lazy 값이 있으면 ValProp 한다.
    • 범위에 완전히 벗어나면 걍 끝낸다.
    • 만약 완전히 범위에 들어가면, Lazy값을 다시 설정한 후에 ValProp하고 끝낸다.
    • 만약 에매하게 걸치면, 반반 나눠서 재귀호출 한다.
    • 이후 계산된 자녀의 값을 더해서 업데이트한다.
  • Query 할때는
    • Lazy 값이 있으면 ValProp 한다.
    • 범위에 완전히 벗어나면 0 리턴
    • 만약 완전히 범위에 들어가면, val값 리턴
    • 범위에 걸치면, 반반 나눠서 재귀호출 한 두 값을 더한다.
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
#include <bits/stdc++.h>
using namespace std;

typedef int IType;
struct Tree {
  IType val, lazy;
};

class SegmentTree {
  vector<Tree> tree;
  void propagate(int node, int start, int end) {
    if(tree[node].lazy) {
      tree[node].val = (end - start + 1) - tree[node].val;
      if(start != end) { // not Leaf
        tree[2*node].lazy = 1 - tree[2*node].lazy;
        tree[2*node+1].lazy = 1 - tree[2*node+1].lazy;
      }
      tree[node].lazy = 0;
    }
  }

public:
  SegmentTree(int n): tree(4*n) {}

  void rangeUpdate(int l, int r, int node, int start, int end) {
    propagate(node, start, end);
    if (r < start || end < l) return;
    if(l <= start && end <= r) {
      tree[node].lazy = 1 - tree[node].lazy;
      propagate(node, start, end);
      return;
    }
    int m = (start + end) / 2;
    rangeUpdate(l, r, node*2, start, m);
    rangeUpdate(l, r, node*2+1, m+1, end);
    tree[node].val = tree[2*node].val + tree[2*node+1].val;
  }

  IType sum(int l, int r, int node, int start, int end) {
    propagate(node, start, end);
    if (r < start || end < l) return 0;
    if(l <= start && end <= r) return tree[node].val;

    int m = (start + end) / 2;
    return sum(l, r, 2*node, start, m) + sum(l, r, 2*node+1, m+1, end);
  }
};

int main() {
  int N, M;
  scanf("%d%d", &N, &M);
  SegmentTree st(N);
  for (int i = 0; i < M; i++) {
    int O, S, T;
    scanf("%d%d%d", &O, &S, &T);
    if (O == 0)
      st.rangeUpdate(S, T, 1, 1, N);
    else
      printf("%d\n", st.sum(S, T, 1, 1, N));
  }
}