BOJ 9213 - 꽤 좋은 수

BOJ 9213 - 꽤 좋은 수

정해가 뭔지 모르겠는데 일단 날먹으로 merge sort tree 를 쓰려고 했더니 MLE가 났다.

이후에 오프라인 쿼리로 숫자들에서 badness를 기준으로 정렬하고 쿼리에서도 이걸 정렬시키고 펜윅트리로 쿼리를 처리했다.

정해는 쿼리가 몇개가 들어오는지 모르겠지만 아마 최대 badness가 작음을 이용해 badness 마다 숫자들을 모아두고 이분탐색 같은걸로 수를 세주는 것 같다.

const int MAX = 1e6;
int dsum[MAX + 1], bad[MAX + 1];
// region FENWICK
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
void pre_calc() {
   for (int i = 1; i <= MAX; i++) {
      for (int j = i + i; j <= MAX; j += i) {
         dsum[j] += i;
      }
   }
   for (int i = 2; i <= MAX; i++) bad[i] = abs(i - dsum[i]);
}

void solve() {
   vector<array<int, 4>> tc;
   for (int t = 1;; t++) {
      int l, r, b;
      cin >> l >> r >> b;
      if (l == 0 && r == 0 && b == 0) break;
      tc.pb({b, l, r, t});
   }
   vector<int> ans(sz(tc));
   sort(all(tc));

   fenwick<int> fenw(MAX + 1);
   vi idx(MAX + 1);
   iota(all(idx), 0);
   sort(all(idx), [&](int i, int j) {
      return bad[i] < bad[j];
   });
   for (int i = 0, j = 0; i < sz(tc); i++) {
      while (j <= MAX && bad[idx[j]] <= tc[i][0]) {
         fenw.update(idx[j], 1);
         j++;
      }
      ans[tc[i][3] - 1] = fenw.query(tc[i][1], tc[i][2]);
   }

   for (int i = 0; i < sz(tc); i++) {
      cout << "Test " << i + 1 << ": " << ans[i] << endl;
   }
}