BOJ 1273 - 샷

BOJ 1273 - 샷

$M$개의 쏘는 횟수에 대해, 쐈을 때의 높이가 아닌 쏜 row가 원래 어디 높이였는지를 구하면 쉽게 풀린다.

이는 세그먼트 트리로 이분탐색을 때려서 $O(N \log^2 N)$에 구해도 되고, 세그먼트 트리에서 K 번째 수를 찾는 테크닉을 써서 $O(N \log N)$에 구할 수도 있다.

여하튼 이걸 구하고나면, 각 블록마다 구간이 세 개 이하씩 나오는 부분들에 대해서 1, 2, 5 점을 구간합 배열이든 lazy propagation 세그먼트 트리든 표시해둔다음에 $M$개의 쏘는 시도에 대해서 합을 구해주면 된다.

template<class T>
struct fenwick {
   int n;
   vector<T> tree;
   fenwick(int n) : n(n) { tree.resize(n + 1); }
   T sum(int i) {
      T ret = 0;
      for (; i; i -= i & -i) ret += tree[i];
      return ret;
   }
   void update(int i, T x) { for (i++; i <= n; i += i & -i) tree[i] += x; }
   T query(int l, int r) { return l > r ? 0 : sum(r + 1) - sum(l); }
};
template<class T>
struct fenwick_point {
   fenwick<T> f;
   fenwick_point(int n) : f(fenwick<T>(n + 1)) {}
   void update(int l, int r, T x) { f.update(l, x), f.update(r + 1, -x); }
   T query(int i) { return f.query(0, i); }
};
template<class T>
struct fenwick_range {
   fenwick<T> d, c;
   fenwick_range(int n) : d(fenwick<T>(n + 1)), c(fenwick<T>(n + 1)) {}
   void update(int l, int r, T x) {
      d.update(l, x), d.update(r + 1, -x), c.update(l, (1 - l) * x), c.update(r + 1, r * x);
   }
   T query(int l, int r) {
      l--;
      return d.query(0, r) * r + c.query(0, r) - (l >= 0 ? d.query(0, l) * l + c.query(0, l) : 0);
   }
};
// endregion
const int MAX = 3e6;
void solve() {
   int n, m;
   cin >> n;
   vector<array<int, 3>> a(n);
   for (int i = 0; i < n; i++) cin >> a[i][0];
   for (int i = 0; i < n; i++) cin >> a[i][1];
   for (int i = 0; i < n; i++) cin >> a[i][2];
   cin >> m;
   vi shot(m);
   fv(shot);

   fenwick<int> fenw(MAX + 1);
   for (int i = 0; i < m; i++) {
      // 비어있는 만큼 위로 올려야함 O(Nlog^2N)
      int l = 1, r = MAX, f = -1;
      while (l <= r) {
         int m = l + (r - l) / 2;
         if (m - fenw.query(0, m) >= shot[i]) r = m - 1, f = m;
         else l = m + 1;
      }
      shot[i] = f;
      fenw.update(shot[i], 1);
   }

   fenwick_range<int> fenw_range(MAX + 1);
   for (int i = 0; i < n; i++) {
      if (a[i][0]) {
         fenw_range.update(0, a[i][0] - 1, 1);
      }
      if (a[i][1]) {
         fenw_range.update(a[i][0], a[i][0] + a[i][1] - 1, 2);
      }
      if (a[i][2]) {
         fenw_range.update(a[i][0] + a[i][1], a[i][0] + a[i][1] + a[i][2] - 1, 5);
      }
   }

   for (int i = 0; i < m; i++) {
      shot[i]--;
      cout << fenw_range.query(shot[i], shot[i]) << endl;
   }
}