BOJ 12876 - 반평면 땅따먹기 2

BOJ 12876 - 반평면 땅따먹기 2

Offline Dynamic Connectivity로 직선을 관리하는 대표적인 문제이다.

세그먼트 트리의 각 노드가 Li-Chao Tree 나 LineContainer 구현체를 갖고있도록 하고 최대값 직선을 관리할 수 있게 한다.

둘 다 Dynamic한 공간복잡도를 가지기 때문에 문제가 되지 않는다.

$[s,e]$ 에 어떤 직선이 추가된다면 해당되는 $\log (e-s)$ 개의 구간에 해당하는 리차오트리들에 모두 그 직선을 추가해준다. 정확히 말하면 이 직선이 영향을 미치는 $3$번 쿼리의 구간이다.

그리고 그냥 순회하면서 이 $3$번 쿼리의 구간에 살아있는 직선들에 대해 모두 쿼리해주면 된다.

업데이트에 세그먼트 트리가 쓰이므로 $O(\log N)$인데, 여기서 리차오트리나 LineCotaniner를 써서 $O(\log ^2N)$에 수행되고,

쿼리는 $3$번 쿼리 $Q$개를 순회하며 그 지점을 포함하는 세그먼트 트리 $O(\log Q)$ 개의 구간에 각각 $O(\log N)$에 쿼리를 날리기 때문에 $O(Q + \log Q \cdot \log N)$ 정도로 쿼리가 가능하다.

int Q = 0;
const int inf = 2e20 + 123;
struct Line {
   int a, b;
   int f(int x) { return a * x + b; }
};
Line base = {0, -inf};
struct LiChaoTree {
   struct Node {
      int l = -1, r = -1;
      Line line = base;
   };

   vector<Node> tree;
   LiChaoTree() {
      tree.pb({});
   }
   void update(int n, int nl, int nr, Line line) {
      Line a = tree[n].line;
      Line b = line;
      // b가 nl에서 더 위에 있는 직선이 되게
      if (a.f(nl) > b.f(nl)) swap(a, b);

      if (b.f(nr) >= a.f(nr)) {
         tree[n].line = b;
         return;
      }

      int mid = nl + (nr - nl) / 2;
      if (b.f(mid) >= a.f(mid)) {
         tree[n].line = b;
         if (tree[n].r == -1) {
            tree[n].r = tree.size();
            tree.push_back({});
         }
         update(tree[n].r, mid + 1, nr, a);
      } else {
         tree[n].line = a;
         if (tree[n].l == -1) {
            tree[n].l = tree.size();
            tree.push_back({});
         }
         update(tree[n].l, nl, mid, b);
      }
   }
   void update(Line line) {
      update(0, -inf, inf, line);
   }
   int query(int n, int nl, int nr, int x) {
      if (n == -1) return -inf;
      if (nl == nr) {
         assert(nl == x);
         return tree[n].line.f(x);
      }
      int mid = nl + (nr - nl) / 2;
      if (x <= mid) return max(tree[n].line.f(x), query(tree[n].l, nl, mid, x));
      else return max(tree[n].line.f(x), query(tree[n].r, mid + 1, nr, x));
   }
   int query(int x) {
      return query(0, -inf, inf, x);
   }
};
struct RawQuery {
   int i, cmd, a, b, cur_time;
};
struct Query {
   int i, x;
};
struct InsertQuery {
   int s, e;
   Line line;
};
vector<RawQuery> rawq;
vector<Query> queries;
vector<InsertQuery> insertq;
vi ans, ansEmpty;
struct ODCSegTree {
   int N;
   vector<LiChaoTree> tree;
   ODCSegTree(int N) : N(N) {
      int size = 1 << int(ceil(log2(N)) + 1);
      tree.resize(size);
   }

   void update(int n, int nl, int nr, int l, int r, Line line) {
      if (nl > r || nr < l) return;
      if (nl >= l && nr <= r) {
         tree[n].update(line);
         return;
      }
      int m = nl + (nr - nl) / 2;

      update(n * 2, nl, m, l, r, line);
      update(n * 2 + 1, m + 1, nr, l, r, line);
   }

   void dnc(int n, int nl, int nr) {
      if (nl == nr) {
         int ret = -inf;
         int m = n;
         while (m >= 1) {
            maxa(ret, tree[m].query(queries[nl].x));
            m /= 2;
         }
         //debug(nl, ret);
         if (ret == -inf) {
            ansEmpty[nl] = 1;
         } else ans[nl] = ret;
         return;
      }
      int m = nl + (nr - nl) / 2;
      dnc(n * 2, nl, m);
      dnc(n * 2 + 1, m + 1, nr);
   }
};

void solve() {
   int n;
   cin >> n;

   for (int i = 0, cmd, a, b, x; i < n; i++) {
      cin >> cmd;
      if (cmd == 1) {
         // 추가
         cin >> a >> b;
         rawq.pb({i, 1, a, b, Q});
      } else if (cmd == 2) {
         // 삭제
         cin >> x, x--;
         rawq.pb({i, 2, x});

         int s = rawq[x].cur_time;
         int e = Q - 1;
         rawq[x].cur_time = -1;
         if (s <= e && e >= 0)
            insertq.push_back({s, e, {rawq[x].a, rawq[x].b}});
      } else {
         // 쿼리
         cin >> x;
         queries.pb({i, x});
         rawq.pb({i, 3, x});
         Q++;
      }
   }
   for (int i = 0; i < n; i++) {
      if (rawq[i].cmd == 1 && rawq[i].cur_time != -1 && Q > 0) {
         insertq.push_back({rawq[i].cur_time, Q - 1, {rawq[i].a, rawq[i].b}});
      }
   }
   ODCSegTree seg_tree(Q);
   for (auto iq: insertq) {
      //debug(iq.s, iq.e, iq.line.a, iq.line.b);
      seg_tree.update(1, 0, Q - 1, iq.s, iq.e, iq.line);
   }
   //debug(Q);
   ans.resize(Q);
   ansEmpty.resize(Q);
   seg_tree.dnc(1, 0, Q - 1);
   for (int i = 0; i < Q; i++) {
      if (ansEmpty[i]) cout << "EMPTY\n";
      else cout << ans[i] << endl;
   }
}