AIOJ

Introduction

Luogu 4097 [HEOI2013]Segment

We need to maintain the following two operations on a Cartesian plane (with forced online processing):

Add a line segment to the plane. Let the index of the $i$ -th inserted segment be $i$ , and let its endpoints be $(x_0,y_0)$ and $(x_1,y_1)$ .
Given a number $k$ , query the index of the segment intersecting the line $x = k$ whose intersection has the largest y-coordinate. If multiple segments have the same largest intersection y-coordinate, output the smallest index. If no segment intersects the given line, output $0$ .

The constraints are: the total number of operations is $1 \leq n \leq 10^5$ , $1 \leq k, x_0, x_1 \leq 39989$ , and $1 \leq y_0, y_1 \leq 10^9$ .

We observe that a conventional segment tree cannot maintain this information effectively. This is where the Li Chao segment tree comes in.

Process

We can transform the task into maintaining the following operations:

Add a linear function with domain $[l,r]$ ;
Given $k$ , among all linear functions whose domains contain $k$ , find the one with the largest value at $x=k$ ; if several functions have the same value, choose the one with the smallest index.

Note

When a segment is vertical to the $x$ -axis, division by zero would occur. Suppose its endpoints are $(x,y_0)$ and $(x,y_1)$ , where $y_0<y_1$ ; insert a linear function with domain $[x,x]$ , namely $f(x)=0\cdot x+y_1$ .

When we see an interval update, we use the standard segment-tree approach to interval problems and give each node a lazy marker. The lazy marker of each node $i$ is a line segment, denoted by $l_i$ , indicating that $l_i$ should be used to update the entire interval represented by that node.

Now suppose we need to insert a segment $f$ and consider a segment-tree interval completely covered by the new segment $f$ . If the interval has no marker, we directly mark it with the segment used for the update.

If the interval already has a marker, the markers are difficult to merge, so we can only push the marker down. However, the child nodes have their own markers and may also conflict, so we recursively push the marker downward.

As shown in the figure, depending on whether the value of the new segment $f$ is greater than that of the original marker $g$ , we can divide the current interval into two subintervals. One of the two subintervals is certainly completely contained in the left or right interval; in other words, of the two segments, one can only become the answer in the left interval or only become the answer in the right interval. We recursively update the corresponding subtree with this segment, and use the other segment as the lazy marker to update the entire interval. This guarantees the complexity of recursively pushing markers down. A segment is pushed down only when it can be the answer only in the left or right interval, so no segment is lost.

More specifically, let the midpoint of the current interval be $m$ . We compare the value of the new segment $f$ at the midpoint with the value of the original optimal segment $g$ at the midpoint.

If the new segment $f$ is better, swap $f$ and $g$ . We then consider the case where $f$ is no better than $g$ at the midpoint:

If $f$ is better at the left endpoint, then $f$ and $g$ must intersect in the left half, so $f$ can be better than $g$ only in the left interval; recurse into the left child to push it down;
If $f$ is better at the right endpoint, then $f$ and $g$ must intersect in the right half, so $f$ can be better than $g$ only in the right interval; recurse into the right child to push it down;
If $g$ is better at both endpoints, then $f$ cannot become the answer, so it need not be pushed down further.

There is one additional case: $f$ and $g$ intersect exactly at the midpoint. In the implementation, it can be treated as the case where $f$ is no better than $g$ at the midpoint; the recursion then descends toward an endpoint where $f$ is better.

Finally, use $g$ as the lazy marker of the current interval.

Push down the marker:

Implementation

constexpr double eps = 1e-9;

int cmp(double x, double y) {  // Floating-point arithmetic introduces precision errors.
  if (x - y > eps) return 1;
  if (y - x > eps) return -1;
  return 0;
}

//...

void upd(int root, int cl, int cr, int u) {  // Update an interval completely covered by the segment.
  int &v = s[root], mid = (cl + cr) >> 1;
  int bmid = cmp(calc(u, mid), calc(v, mid));
  if (bmid == 1 || (!bmid && u < v))  // Remember to compare segment indices in this problem.
    swap(u, v);
  int bl = cmp(calc(u, cl), calc(v, cl)), br = cmp(calc(u, cr), calc(v, cr));
  if (bl == 1 || (!bl && u < v)) upd(root << 1, cl, mid, u);
  if (br == 1 || (!br && u < v)) upd(root << 1 | 1, mid + 1, cr, u);
  // At most one of the two conditions above holds, which guarantees the Li Chao tree's time complexity.
}

Split a segment:

Implementation

void update(int root, int cl, int cr, int l, int r,
            int u) {  // Locate the interval completely covered by the inserted segment.
  if (l <= cl && cr <= r) {
    upd(root, cl, cr, u);  // The current interval is completely covered; update its marker.
    return;
  }
  int mid = (cl + cr) >> 1;
  if (l <= mid) update(root << 1, cl, mid, l, r, u);  // Recursively split the interval.
  if (mid < r) update(root << 1 | 1, mid + 1, cr, l, r, u);
}

Note that a lazy marker is not equivalent to the segment with the largest value at the midpoint of the interval.

As shown in the figure, after the yellow segment is added, only the marker of the red node is updated, while the markers of the green nodes remain unchanged. However, at the midpoints of the second, third, and fourth green intervals, the yellow segment clearly has the largest value.

When querying, we can use the idea of persistent markers: among the marked segments of all segment-tree intervals containing $x$ (at most $O(\log n)$ intervals), compare their values to obtain the final answer.

Query:

Implementation

pdi query(int root, int l, int r, int d) {  // Query.
  if (r < d || d < l) return {0, 0};
  int mid = (l + r) >> 1;
  double res = calc(s[root], d);
  if (l == r) return {res, s[root]};
  return pmax({res, s[root]}, pmax(query(root << 1, l, mid, d),
                                   query(root << 1 | 1, mid + 1, r, d)));
}

According to the description above, a query takes $O(\log n)$ time. During insertion, we split the original segment into $O(\log n)$ intervals, and for each interval spend another $O(\log n)$ time recursively pushing the marker down, so insertion takes $O(\log^2 n)$ time.

[HEOI2013]Segment Reference code

#include <iostream>
constexpr int MOD1 = 39989;
constexpr int MOD2 = 1000000000;
constexpr int MAXT = 40000;
using namespace std;
using pdi = pair<double, int>;

constexpr double eps = 1e-9;

int cmp(double x, double y) {
  if (x - y > eps) return 1;
  if (y - x > eps) return -1;
  return 0;
}

struct line {
  double k, b;
} p[100005];

int s[160005];
int cnt;

double calc(int id, int d) { return p[id].b + p[id].k * d; }

void add(int x0, int y0, int x1, int y1) {
  cnt++;
  if (x0 == x1)  // Handle the case of a vertical segment separately.
    p[cnt].k = 0, p[cnt].b = max(y0, y1);
  else
    p[cnt].k = 1.0 * (y1 - y0) / (x1 - x0), p[cnt].b = y0 - p[cnt].k * x0;
}

void upd(int root, int cl, int cr, int u) {  // Update an interval completely covered by the segment.
  int &v = s[root], mid = (cl + cr) >> 1;
  int bmid = cmp(calc(u, mid), calc(v, mid));
  if (bmid == 1 || (!bmid && u < v)) swap(u, v);
  int bl = cmp(calc(u, cl), calc(v, cl)), br = cmp(calc(u, cr), calc(v, cr));
  if (bl == 1 || (!bl && u < v)) upd(root << 1, cl, mid, u);
  if (br == 1 || (!br && u < v)) upd(root << 1 | 1, mid + 1, cr, u);
}

void update(int root, int cl, int cr, int l, int r,
            int u) {  // Locate the interval completely covered by the inserted segment.
  if (l <= cl && cr <= r) {
    upd(root, cl, cr, u);
    return;
  }
  int mid = (cl + cr) >> 1;
  if (l <= mid) update(root << 1, cl, mid, l, r, u);
  if (mid < r) update(root << 1 | 1, mid + 1, cr, l, r, u);
}

pdi pmax(pdi x, pdi y) {  // Maximum function for pairs.
  if (cmp(x.first, y.first) == -1)
    return y;
  else if (cmp(x.first, y.first) == 1)
    return x;
  else
    return x.second < y.second ? x : y;
}

pdi query(int root, int l, int r, int d) {  // Query.
  if (r < d || d < l) return {0, 0};
  int mid = (l + r) >> 1;
  double res = calc(s[root], d);
  if (l == r) return {res, s[root]};
  return pmax({res, s[root]}, pmax(query(root << 1, l, mid, d),
                                   query(root << 1 | 1, mid + 1, r, d)));
}

int main() {
  ios::sync_with_stdio(false);
  int n, lastans = 0;
  cin >> n;
  while (n--) {
    int op;
    cin >> op;
    if (op == 1) {
      int x0, y0, x1, y1;
      cin >> x0 >> y0 >> x1 >> y1;
      x0 = (x0 + lastans - 1 + MOD1) % MOD1 + 1,
      x1 = (x1 + lastans - 1 + MOD1) % MOD1 + 1;
      y0 = (y0 + lastans - 1 + MOD2) % MOD2 + 1,
      y1 = (y1 + lastans - 1 + MOD2) % MOD2 + 1;
      if (x0 > x1) swap(x0, x1), swap(y0, y1);
      add(x0, y0, x1, y1);
      update(1, 1, MOD1, x0, x1, cnt);
    } else {
      int x;
      cin >> x;
      x = (x + lastans - 1 + MOD1) % MOD1 + 1;
      cout << (lastans = query(1, 1, MOD1, x).second) << endl;
    }
  }
  return 0;
}

Merging

As with merging ordinary segment trees, we define the following process for merging two Li Chao segment-tree nodes $u,v$ , using $u$ as the new root.

If $v$ is empty, end the process.
If $u$ is empty, copy $v$ to $u$ .
Insert the segment corresponding to $v$ into the subtree rooted at $u$ .
Recursively merge the corresponding left and right subtrees of $u,v$ .

If the total number of nodes involved in merging several Li Chao segment trees is $n$ , the complexity is $O(n\log n)$ : for any node corresponding to a segment in the tree, each time it is moved, either its depth increases by $+1$ or it is directly removed from the tree. Both operations cost $O(1)$ , and the depth of each node is at most $O(\log n)$ , giving the stated complexity.

Implementation

void upd(int &root, int cl, int cr,
         int u) {  // Merge multiple Li Chao trees; use dynamic node creation.
  static int idx = 0;
  if (!root) {
    s[root = ++idx] = u;
    return;
  }
  int &v = s[root], mid = (cl + cr) >> 1;
  int bmid = cmp(calc(u, mid), calc(v, mid));
  if (bmid == 1 || (!bmid && u < v)) swap(u, v);
  int bl = cmp(calc(u, cl), calc(v, cl)), br = cmp(calc(u, cr), calc(v, cr));
  if (bl == 1 || (!bl && u < v)) upd(ls[root], cl, mid, u);
  if (br == 1 || (!br && u < v)) upd(rs[root], mid + 1, cr, u);
}

int merge(int &u, int &v, int l, int r) {
  if (!u || !v) {
    return u + v;
  }
  if (l == r) {
    int b = cmp(calc(s[v], l), calc(s[u], l));
    if (b == 1 || (!b && s[v] < s[u])) return v;
    return u;
  }
  upd(u, l, r, s[v]);
  int mid = (l + r) >> 1;
  ls[u] = merge(ls[u], ls[v], l, mid);
  rs[u] = merge(rs[u], rs[v], mid + 1, r);
  return u;
}

Exercises

「JSOI2008」Blue Mary Opens a Company

「CodeChef」TSUM2 Sum on Tree

「USACO13MAR」Hill Walk G

「CF932F」Escape Through Leaf

Li Chao Segment Tree

Introduction

Process

Merging

Exercises