BOJ 10650 - Marathon

BOJ 10650 - Marathon

$i$ 번째 위치를 $(x,y)$ 로 바꾸는 쿼리가 들어온다.

$i \to j$ 의 sub-route에서 최소 이동 거리(그 중 시작점과 끝점이 아닌 하나를 skip할 수 있다고 했을 때)

$i$에서 $i+1$ 의 거리 차이를 각각 세그먼트 트리의 인덱스 $i$에 저장해둔다.

다른 세그먼트 트리로 $i$ 번째가 사라졌을 때 $i-1, i+1$ 번째가 이어지며 최대로 이득이 생기는 것을 관리한다.

쿼리는 $A, B$ 에의 $[A, B-1]$ 거리 합 - 최대로 뺄 수 있는 값 이 된다.

업데이트도 두 세그먼트 트리를 잘 관리하며 해주자.

void solve() {
   int n, q;
   cin >> n >> q;
   vector<pi> p(n);
   for (auto &[x, y]: p) cin >> x >> y;
   auto dist = [&](int i, int j) {
      return abs(p[i].fi - p[j].fi) + abs(p[i].se - p[j].se);
   };
   auto benefit = [&](int i) {
      int original = dist(i - 1, i) + dist(i, i + 1);
      int removed = dist(i - 1, i + 1);
      return original - removed;
   };
   seg_tree<int> seg(n), seg_benefit(n);
   for (int i = 1; i < n - 1; i++) seg_benefit.update(i, benefit(i));
   for (int i = 0; i < n - 1; i++) seg.update(i, dist(i, i + 1));
   while (q--) {
      string cmd;
      cin >> cmd;
      if (cmd == "Q") {
         int i, j;
         cin >> i >> j, i--, j--;
         if (i == j) cout << 0 << endl;
         else if (i + 1 == j) cout << dist(i, j);
         else {
            int sum = seg.query(i, j - 1).sum;
            debug(seg_benefit.query(2, 2).max);
            cout << sum - max(0, seg_benefit.query(i + 1, j - 1).max) << endl;
         }
      } else {
         int i, x, y;
         cin >> i >> x >> y, i--;
         p[i] = {x, y};
         if (i != 0 && i != n - 1) seg_benefit.update(i, benefit(i));
         if (i != 0) seg.update(i - 1, dist(i - 1, i));
         if (i - 1 >= 1) seg_benefit.update(i - 1, benefit(i - 1));
         if (i != n - 1) seg.update(i, dist(i, i + 1));
         if (i + 1 < n - 1) seg_benefit.update(i + 1, benefit(i + 1));
      }
   }
}