[Algorithm] C++ 백준 17474번 : 수열과 쿼리

아이디어 요약

쿼리
- 1 L R X: 모든 i ∈ [L, R]에 대해 A[i] = min(A[i], X) (range chmin)
- 2 L R: max(A[L..R])
- 3 L R: sum(A[L..R])
Segment Tree Beats를 사용해 각 노드에 (mx, se, cnt, sum)을 유지합니다.
- mx: 구간 최댓값, se: 구간 내 두 번째 최댓값, cnt: 최댓값의 개수, sum: 합
- chmin(x)을 적용할 때 x > se이면 전체 노드에 한 번에 반영 가능합니다.
- 필요 시 자식에게만 전파(push)하고 다시 병합(merge)합니다.
합은 long long으로 누적하며, 빠른 입출력으로 1e6 규모 입출력과 연산을 처리합니다.

C++ 풀이

  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
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
// 42jerrykim.github.io에서 더 많은 정보를 확인 할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

#ifdef _WIN32
#define getchar_unlocked getchar
#define putchar_unlocked putchar
#endif

struct FastScanner {
  static const int BUFSIZE = 1 << 20;
  int idx = 0, size = 0;
  char buf[BUFSIZE];
  inline char read() {
    if (idx >= size) {
      size = (int)fread(buf, 1, BUFSIZE, stdin);
      idx = 0;
      if (size == 0) return 0;
    }
    return buf[idx++];
  }
  template <class T>
  bool nextInt(T &out) {
    char c; T sign = 1; T x = 0; c = read();
    if (!c) return false;
    while (c!='-' && (c<'0' || c>'9')) { c = read(); if (!c) return false; }
    if (c=='-') { sign = -1; c = read(); }
    for (; c>='0' && c<='9'; c = read()) x = x*10 + (c - '0');
    out = x * sign;
    return true;
  }
} fs;

inline void writeInt64(long long x) {
  if (x == 0) { putchar_unlocked('0'); putchar_unlocked('\n'); return; }
  if (x < 0) { putchar_unlocked('-'); x = -x; }
  char s[24]; int n = 0;
  while (x) { s[n++] = char('0' + (x % 10)); x /= 10; }
  while (n--) putchar_unlocked(s[n]);
  putchar_unlocked('\n');
}

struct Node {
  long long sum;
  int mx;
  int se;   // second max
  int cnt;  // count of max
};

static const int NEG_INF = INT_MIN;
int N;
vector<Node> seg;
vector<int> A;

inline Node mergeNode(const Node &L, const Node &R) {
  Node res;
  res.sum = L.sum + R.sum;
  if (L.mx == R.mx) {
    res.mx = L.mx;
    res.cnt = L.cnt + R.cnt;
    res.se = max(L.se, R.se);
  } else if (L.mx > R.mx) {
    res.mx = L.mx;
    res.cnt = L.cnt;
    res.se = max(L.se, R.mx);
  } else { // R.mx > L.mx
    res.mx = R.mx;
    res.cnt = R.cnt;
    res.se = max(L.mx, R.se);
  }
  return res;
}

inline void apply_chmin(int p, int x) {
  Node &u = seg[p];
  if (x >= u.mx) return;
  // This function must be called only when x > u.se
  long long dec = 1LL * (u.mx - x) * u.cnt;
  u.sum -= dec;
  u.mx = x;
}

inline void push(int p) {
  int lc = p << 1, rc = lc | 1;
  if (seg[p].mx < seg[lc].mx) apply_chmin(lc, seg[p].mx);
  if (seg[p].mx < seg[rc].mx) apply_chmin(rc, seg[p].mx);
}

void build(int p, int l, int r) {
  if (l == r) {
    seg[p].sum = A[l];
    seg[p].mx = A[l];
    seg[p].se = NEG_INF;
    seg[p].cnt = 1;
    return;
  }
  int m = (l + r) >> 1;
  build(p << 1, l, m);
  build(p << 1 | 1, m + 1, r);
  seg[p] = mergeNode(seg[p << 1], seg[p << 1 | 1]);
}

void range_chmin(int p, int l, int r, int ql, int qr, int x) {
  if (qr < l || r < ql || seg[p].mx <= x) return;
  if (ql <= l && r <= qr && seg[p].se < x) {
    apply_chmin(p, x);
    return;
  }
  push(p);
  int m = (l + r) >> 1;
  range_chmin(p << 1, l, m, ql, qr, x);
  range_chmin(p << 1 | 1, m + 1, r, ql, qr, x);
  seg[p] = mergeNode(seg[p << 1], seg[p << 1 | 1]);
}

int range_max(int p, int l, int r, int ql, int qr) {
  if (qr < l || r < ql) return INT_MIN;
  if (ql <= l && r <= qr) return seg[p].mx;
  push(p);
  int m = (l + r) >> 1;
  return max(range_max(p << 1, l, m, ql, qr),
             range_max(p << 1 | 1, m + 1, r, ql, qr));
}

long long range_sum(int p, int l, int r, int ql, int qr) {
  if (qr < l || r < ql) return 0LL;
  if (ql <= l && r <= qr) return seg[p].sum;
  push(p);
  int m = (l + r) >> 1;
  return range_sum(p << 1, l, m, ql, qr) +
         range_sum(p << 1 | 1, m + 1, r, ql, qr);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  if (!fs.nextInt(N)) return 0;
  A.assign(N + 1, 0);
  for (int i = 1; i <= N; ++i) fs.nextInt(A[i]);

  int M; fs.nextInt(M);
  seg.assign(4 * (N + 5), Node{0, 0, 0, 0});
  build(1, 1, N);

  for (int i = 0; i < M; ++i) {
    int t; fs.nextInt(t);
    if (t == 1) {
      int L, R, X; fs.nextInt(L); fs.nextInt(R); fs.nextInt(X);
      range_chmin(1, 1, N, L, R, X);
    } else if (t == 2) {
      int L, R; fs.nextInt(L); fs.nextInt(R);
      int ans = range_max(1, 1, N, L, R);
      writeInt64(ans);
    } else { // t == 3
      int L, R; fs.nextInt(L); fs.nextInt(R);
      long long ans = range_sum(1, 1, N, L, R);
      writeInt64(ans);
    }
  }
  return 0;
}