BOJ 17076 - 망가진 데이터

BOJ 17076 - 망가진 데이터

내 풀이

난 정점 $N$을 기준으로 $N' \coloneqq 1 \to N$ 으로 스위핑하며 풀었는데 이 풀이는 상당히 구현할 것도 많고 까다롭다.

무려 세그먼트 트리를 $3$개나 써야 했고, 코드만 첨부하고 설명은 생략한다.

template<class T>
struct seg_tree {
private:
   const T INF = numeric_limits<T>::max() >> 1;
   struct node {
      T sum = 0, min = 0, max = 0;
      node(T v) : sum(v), min(v), max(v) {}
      node(T sum, T min, T max) : sum(sum), min(min), max(max) {}
   };
   const node identity{0, 0, 0};
   int N;
   vector<node> tree;
   node merge(node l, node r) {
      node ret = {l.sum + r.sum, min(l.min, r.min), max(l.max, r.max)};
      return ret;
   }
   void update(int n, int nl, int nr, int i, T v) {
      if (nl > i || nr < i) return;
      if (nl == nr) {
         tree[n] = merge(tree[n], node(v)); // diff or assign?
         return;
      }
      int m = (nl + nr) >> 1;
      update(n * 2, nl, m, i, v);
      update(n * 2 + 1, m + 1, nr, i, v);
      tree[n] = merge(tree[n * 2], tree[n * 2 + 1]);
   }
   node query(int n, int nl, int nr, int l, int r) {
      if (nl > r || nr < l) return identity;
      if (nl >= l && nr <= r) return tree[n];
      int m = (nl + nr) >> 1;
      return merge(query(n * 2, nl, m, l, r), query(n * 2 + 1, m + 1, nr, l, r));
   }
public:
   seg_tree(int N) : N(N) {
      int tree_size = 1 << ((int) ceil(log2(N)) + 1);
      tree = vector<node>(tree_size, identity);
   }
   void update(int i, T v) { update(1, 0, N - 1, i, v); }
   node query(int l, int r) { return query(1, 0, N - 1, l, r); };
};
void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);
   vi mn(n);
   mn[0] = a[0];
   for (int i = 1; i < n; i++) mn[i] = min(mn[i - 1], a[i]);

   seg_tree<int> seg(n), seg3(n), seg2(200001);
   vi idx(n);
   iota(all(idx), 0);
   sort(all(idx), [&](int i, int j) { return a[i] < a[j]; });

   vi m_idx_possible(n, 1e9);
   for (int i = n - 1; i >= 0; i--) {
      int back_cnt = n - 1 - (i + 1) + 1;
      if (back_cnt / 2 < a[i]) {

      } else {

         int l = 0, r = 1e6, order = -1;
         while (l <= r) {
            int m = l + (r - l) / 2;
            if (seg2.query(1, m).sum >= a[i] * 2) {
               order = m, r = m - 1;
            } else l = m + 1;
         }
         m_idx_possible[i] = order;
         assert(~order);
      }
      seg2.update(a[i], 1);
   }
   vi midx(n);
   iota(all(midx), 0);
   sort(all(midx), [&](int i, int j) {
      return m_idx_possible[i] < m_idx_possible[j];
   });
   pi ans = {-1, -1};
   vi first_idx(200001, -1);
   for (int i = 0; i < n; i++) if (first_idx[a[i]] == -1) first_idx[a[i]] = i;
   for (int i = 1, j = 0, mj = 0; i <= 200000; i++) {
      while (j < n && a[idx[j]] <= i) {
         seg.update(idx[j], 1);
         j++;
      }
      while (mj < n && m_idx_possible[midx[mj]] <= i) {
         seg3.update(midx[mj], a[midx[mj]]);
         mj++;
      }
      if (first_idx[i] == -1) continue;

      int n_idx = first_idx[i];
      int m_mx = seg3.query(n_idx + 1, n - 1).max;
      if (m_mx) {
         maxa(ans, mp(i, m_mx));
      }
      // n_idx 보다 뒤에 있는 것 중 m_idx를 고르고 m_idx 뒤에 a[m_idx] * 2 개 이상이 있어야 한다.
      // m_idx 가 가능하게 되는 시점도 스위핑?
   }
   if (ans.fi == -1) cout << -1;
   else cout << ans.fi << ' ' << ans.se;
}

다른 풀이

간선 개수 $M$을 기준으로 스위핑을 하는 것이 더 쉽다.

$M$의 후보로 $a_i$가 작은 것부터 살펴보자.

일단 $M=a_i$가 되려면 $i+1 \sim K$ 까지 수들이 $2a_i$개 이상이여야 하고, 어떤 $N$으로 $a_j ~ (j<i)$ 를 골랐을 때, 그 $2a_i$ 개의 수들이 모두 $a_j$ 이하여야 한다.

그럼 $j$는 $a_j$가 항상 가장 큰 것을 고르는게 이득이다.

따라서 $N$의 후보는 $M=a_i$ 을 정하면 항상 고정된다.

$1 \sim i-1$ 까지 $a_j$ 중 가장 큰 것을 $N$ 으로 결정해주면 된다.

게다가 문제에서도 $(N, M)$의 최대값을 구하라니 문제의 조건과도 아주 스무스하게 연결된다.

그래서 왼쪽에 가장 큰 $N$ 이하의 수 개수가 $i+1 \sim K$ 까지 몇개가 있는지 보면 되는데, 이건 Segment Tree로 구현하거나 Merge Sort Tree를 쓰면 빠르게 쿼리할 수 있다.