BOJ 28031 - Milk Sum

BOJ 28031 - Milk Sum

풀이는 쉽게 보인다.

오프라인 쿼리없이 $a_i$ 를 작은순으로 정렬해두고 $T$를 구하는게 최적이므로, $i, j$가 들어왔을 때 $a_i$ 가 몇 번째 순서인지, $j$ 는 정렬된 $a$ 에서 몇 번째 순서인지를 구한다음,

미리 만들어둔 정답과 구간합 배열을 이용해서 $1$ 씩 증감하는 부분을 더하고 빼고 정답에 $j \cdot$새로운 인덱스의 위치

를 더해준 것이 쿼리의 정답이다.

void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);
   vi idx(n), idx_rev(n);
   iota(all(idx), 0);
   sort(all(idx), [&](int i, int j) { return a[i] < a[j]; });
   for (int i = 0; i < n; i++) idx_rev[idx[i]] = i;
   vi psum(n + 1);
   for (int i = 0; i < n; i++) psum[i + 1] = psum[i] + a[idx[i]];
   auto sum = [&](int l, int r) {
      if (l > r) return 0ll;
      return psum[r + 1] - psum[l];
   };
   ll ans = 0;
   for (int i = 0; i < n; i++) ans += (i + 1) * a[idx[i]];
   int q;
   cin >> q;

   vi b = a;
   sort(all(b));

   while (q--) {
      int i, j;
      cin >> i >> j, i--;
      int cur_idx = idx_rev[i];

      if (a[i] == j) {
         cout << ans << endl;
         continue;
      }
      ll tmp = ans;
      tmp -= (cur_idx + 1) * a[i];
      if (a[i] < j) {
         int new_idx = ubi(b, j);
         tmp -= sum(cur_idx + 1, new_idx - 1);
         tmp += j * (new_idx);
      } else {
         int new_idx = ubi(b, j);
         tmp += sum(new_idx, cur_idx - 1);
         tmp += j * (new_idx + 1);
      }
      cout << tmp << endl;
   }
}