BOJ14733: 행사장 대여 (Large)

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

  • 하루 죙일 시간을 소모한 문제.
  • 핵심은 Lazy Propagation인데, 해당 노드가 가진 범위의 활성화된 범위를 관리하는것.
    • 기존 Lazy Propagation은 lazy값이 있을때 그냥 단순히 값을 산출하고 propagation 하면 됨.
    • 이번 경우는 해당 노드 자체가 몇번 켜졌는지 관리하는것.
    • 그러므로 lazy 값이라는게 없고, 그냥 몇번 덮였었는지로 판단하면 됨.
    • 그리고 전체 덮인것을 자녀 노드로 propgation 안함으로써, 추가 계산을 막게 됨.
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
#include <bits/stdc++.h>
using namespace std;

struct Tree {
  int val, cnt;
};

class SegmentTree {
  vector<Tree> tree;

  void merge(int node, int start, int end) {
    if(tree[node].cnt)
      tree[node].val = (end - start + 1);
    else if(start != end)
      tree[node].val = tree[2*node].val + tree[2*node+1].val;
    else
      tree[node].val = 0;
  }

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

  void update(int node, int start, int end, int l, int r, int v) {
    if(r < start || end < l) return;
    if(l <= start && end <= r) {
      tree[node].cnt += v;
      merge(node, start, end);
      return;
    }
    int m = (start + end) / 2;
    update(2*node, start, m, l, r, v);
    update(2*node+1, m+1, end, l, r, v);
    merge(node, start, end);
  }

  int query() {
    return tree[1].val;
  }
};

enum Cmd { ADD, DEL };
struct Event {
  Cmd cmd;
  int x, y1, y2;
  bool operator<(const Event &b) const {
    return x < b.x;
  }
};

int main() {
  int N;
  scanf("%d", &N);
  vector<Event> events;
  for(int i = 0; i < N; i++) {
    int x1, y1, x2, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    events.push_back({ADD, x1, y1, y2});
    events.push_back({DEL, x2, y1, y2});
  }
  sort(events.begin(), events.end());

  const int O = 50000, S = 0, E = 100000;
  events.push_back({ADD, O+1, 0, 0});
  long long ans = 0, prevX = -O;
  SegmentTree st(E);
  for(auto [cmd, x, y1, y2] : events) {
    if(x != prevX) {
      ans += (x - prevX) * st.query();
      prevX = x;
    }
    st.update(1, S, E, y1+O, y2+O-1, cmd == ADD ? 1 : -1);
  }
  cout << ans;
}