Lichao Segment Tree

The data structure used to process the segments solves the online problem with both operations:

• Insert a line segment

• Query for the highest segment of a horizontal coordinate

principle

The segment tree maintains the transverse coordinates, and each node stores the optimal segment of the interval represented by the node, which needs to be satisfied:

• The horizontal coordinates completely cover this interval.

• The segment that satisfies the previous condition is the highest at the midpoint of the interval.

The optimal segment here can be interpreted as a special permanent marker.

insert

The specified horizontal coordinate size is an integer of \(O(Mx)\).

We divide the segments to be inserted into \(O(O(\log Mx))\) segments, just like a normal segment tree, and insert them separately.

For a segment that corresponds to a node, we first calculate the influence of the new segment on the optimal segment of the node.

Comparing the value of the midpoint between the new segment and the original optimal segment directly to get the optimal segment of the interval.

• If the new segment is not optimal:

If there is no intersection between the new segment and the optimal segment, the insertion ends directly because it is lower everywhere than the optimal segment.

If there is an intersection, then on one side of the intersection, the new segment is above the optimal segment. We recursively go to the son at the intersection to continue processing and insert the new segment into the son.

• If the new segment is the optimal segment:

If there is no intersection between the new segment and the optimal segment, the optimal segment is modified directly because the original optimal segment can be completely replaced in this interval.

If there is an intersection, then on one side of the intersection, the new segment is below the original segment. We recursively go to the son at the intersection to continue processing and insert the original segment into the son.

query

When querying, attention should be paid to the information of all nodes on the query path. This is the biggest feature of marker permanence. For each optimal line segment, the longitude coordinate of the target horizontal coordinate is calculated, taking the largest one.

Complexity

Inserts \(O(\log Mx)\) segments every time a line segment is inserted, and at each insertion, the recursive \(O(\log Mx)\) layer has a unique branch for each layer, so the insertion complexity is \(O(\log^2 Mx)\).

Queries require only the recursive \(O(\log Mx)\) layer to find the answer, so it is \(O(\log Mx)\).

Correctness

First come to the conclusion that every node of Lichaothu does not necessarily have the optimal segment, but its true optimal segment must be the optimal segment rooted at at least one node on this node path. Moreover, the query result of Li Hypertree is correct.

This conclusion fits perfectly with the spirit of marking permanence. Combined with the insertion process, we select the optimal segment that modifies only one node for the case where the segment is higher than the original optimal segment, and then return. It means that for all queries within this node interval, the original segment can be replaced by a new segment calculation.

This process results in segments that do not update the optimal segments for all their sons during insertion. This is why the segment stored at each node is not necessarily the optimal segment.

We use induction to explain the correctness of the query, assuming that the query for all coordinates on the plum supertree is correct before insertion. After insertion, because the answer to the query in the current interval can no longer be the original line segment, the existence of the original line segment is meaningless. We change the optimal line segment of this node into a new line segment, so that in \(O(\log Mx)\) segments that each query in the interval may recurse as the answer, the original line segment is replaced with a new line segment. Because the original query is correct, the answer must be in these segments, and because the new segment must be better than the original segment in this interval, the answer must be correct.

code implementation

Because the constant for calculating the intersection point is large, we can qualitatively determine the location of the intersection point based on whether the segment to be inserted is the optimal segment and the slope of the two segments, which can be preprocessed.

There are two choices because the constants for determining whether to intersect are large. The first is to determine whether to intersect to prune, the second is not to determine whether to intersect, because redundant recursion does not affect correctness and does not reduce code difficulty.

We find that only two lines (the two sentences that determine the height of two segments at the end) need to be added to the second type of writing to become the first. The first way of writing allows Template Title More than doubles efficiency. (\(1.29s rightarrow 579ms)))

const double Ep(0.0000000001);
const unsigned Mod(39989), Inf(1000000000);
double Now(0);
unsigned A, B, Ans(0);
inline char Eq(double x, double y) { return (x + Ep >= y) && (y + Ep >= x); }
struct Seg {
  double K;
  unsigned Lx, Ly, Rx, Ry;
  inline void In() {
    Lx = ((RD() + Ans - 1) % Mod) + 1, Ly = ((RD() + Ans - 1) % Inf) + 1;
    Rx = ((RD() + Ans - 1) % Mod) + 1, Ry = ((RD() + Ans - 1) % Inf) + 1;
    if (Lx > Rx) swap(Lx, Rx), swap(Ly, Ry);
    K = ((double)Ry - Ly) / (Rx - Lx);
  }
  inline double Get(unsigned x) {
    if (Rx == Lx) return max(Ly, Ry);
    return Ly + ((((double)Ry - Ly)) * (x - Lx) / (Rx - Lx));
  }
}S[100005], * Best;
struct Node {
  Seg* Mx;
  Node* LS, * RS;
  inline void Insert(unsigned L, unsigned R, Seg* Cur) {
    if (L == R) {
      if (Mx > S + 100000) { Mx = Cur; return; }
      double CM(Cur->Get(L)), XM(Mx->Get(L));
      if (Eq(CM, XM)) { Mx = min(Mx, Cur); return; }
      if (CM > XM) Mx = Cur; return;
    }
    unsigned Mid((L + R) >> 1);
    if ((A <= L) && (R <= B)) {
      if (Mx > S + 100000) { Mx = Cur; return; }
      double CM(Cur->Get(Mid)), XM(Mx->Get(Mid));
      if (Eq(CM, XM)) {
        if (Eq(Cur->K, Mx->K)) { Mx = min(Mx, Cur); return; }
        if (Cur < Mx) {
          if (Cur->K > Mx->K) LS->Insert(L, Mid, Mx);
          else RS->Insert(Mid + 1, R, Mx);
        }
        else {
          if (Cur->K > Mx->K) RS->Insert(Mid + 1, R, Cur);
          else LS->Insert(L, Mid, Cur);
        }
        Mx = min(Mx, Cur);
        return;
      }
      if (CM > XM) {
        if((Cur->Get(L) + Ep > Mx->Get(L)) && (Cur->Get(R) + Ep > Mx->Get(L))) {Mx = Cur;return;}
        if (Cur->K > Mx->K) LS->Insert(L, Mid, Mx);
        else RS->Insert(Mid + 1, R, Mx);
        Mx = Cur;return;
      }
      if((Mx->Get(L) + Ep > Cur->Get(L)) && (Mx->Get(R) + Ep > Cur->Get(L))) return;
      if (Cur->K > Mx->K) return RS->Insert(Mid + 1, R, Cur);
      else return LS->Insert(L, Mid, Cur);
    }
    if (A <= Mid) LS->Insert(L, Mid, Cur);
    if (Mid < B) RS->Insert(Mid + 1, R, Cur);
  }
  inline void Qry(unsigned L, unsigned R) {
    double Tmp((Mx <= S + 100000) ? Mx->Get(A) : -1);
    if (Eq(Tmp, Now)) Best = min(Best, Mx);
    else if (Tmp > Now) Best = Mx, Now = Tmp;
    if (L == R) return;
    unsigned Mid((L + R) >> 1);
    if (A <= Mid) LS->Qry(L, Mid);
    else RS->Qry(Mid + 1, R);
  }
}N[80000], * CntN(N);
inline void Build(Node* x, unsigned L, unsigned R) {
  x->Mx = S + 2000000;
  if (L == R) return;
  unsigned Mid((L + R) >> 1);
  Build(x->LS = ++CntN, L, Mid);
  Build(x->RS = ++CntN, Mid + 1, R);
}
unsigned m, n, Cnt(0);
signed main() {
  n = RD(), Build(N, 1, Mod);
  for (unsigned i(1); i <= n; ++i)
    if (RD()) S[++Cnt].In(), A = S[Cnt].Lx, B = S[Cnt].Rx, N->Insert(1, Mod, S + Cnt);
    else A = ((RD() + Ans - 1) % Mod) + 1, Best = NULL, Now = 0, N->Qry(1, Mod), Ans = Best - S, printf("%u\n", Ans = ((Ans > 0x3f3f3f3f) ? 0 : Ans));
  return Wild_Donkey;
}

Extend to Line

If a straight line is treated as a segment between the root nodes of a segment tree with the minimum and maximum horizontal coordinates and maintained by a Lie supertree, the insertion of this problem becomes \(O(\log Mx)\). Because each segment is divided into only one segment to insert.

Below is the straight-line version of Plum Supertree Template Title There is a hole in this question, that is, when the intercept of a straight line is actually the value of \(y\) when \(x = 1\), the input data needs to be subtracted by a slope to be used as the intercept.

Tip: Strong floating-point integers are converted to integers, which erase directly the part after the decimal point of an absolute value, that is, \(2.9 \rightarrow 2\), \(2.1 \rightarrow 2\), \(-2.9 \rightarrow-2), \(-2.1 \rightarrow 2\).

This question has a limited degree of optimization in determining intersection (\(767ms \rightarrow 626ms))), mainly due to the lower percentage of time spent in insertion operations.

const double Ep(0.0000001);
double Ans(0);
unsigned a[10005], m, n;
unsigned A, B, C, D, t;
unsigned Cnt(0), Tmp(0);
char IO[10];
struct Seg {
  double Y0, K;
  inline void Inp() { scanf("%lf%lf", &Y0, &K), Y0 -= K; }
  inline double Get(unsigned x) { return Y0 + K * x; }
}S[100005];
struct Node {
  Seg* Mx;
  Node* LS, * RS;
  inline void Insert(unsigned L, unsigned R, Seg* x) {
    if (!Mx) { Mx = x; return; }
    if (L == R) { if (x->Get(L) > Mx->Get(L)) Mx = x; return; }
    unsigned Mid((L + R) >> 1);
    if (x->Get(Mid) > Mx->Get(Mid)) {
      if ((x->Get(L) + Ep < Mx->Get(L)) || (x->Get(R) + Ep < Mx->Get(R))) {
        if (x->K > Mx->K) LS->Insert(L, Mid, Mx);
        else RS->Insert(Mid + 1, R, Mx);
      }
      Mx = x;
    }
    else {
      if ((Mx->Get(L) + Ep < x->Get(L)) || (Mx->Get(R) + Ep < x->Get(R))) {
        if (x->K > Mx->K) RS->Insert(Mid + 1, R, x);
        else LS->Insert(L, Mid, x);
      }
    }
  }
  inline void Find(unsigned L, unsigned R) {
    if (Mx) Ans = max(Ans, Mx->Get(A));
    if (L == R) return;
    unsigned Mid((L + R) >> 1);
    if (A <= Mid) LS->Find(L, Mid);
    else RS->Find(Mid + 1, R);
  }
}N[100005], * CntN(N);
inline void Build(Node* x, unsigned L, unsigned R) {
  if (L == R) return;
  unsigned Mid((L + R) >> 1);
  Build(x->LS = ++CntN, L, Mid);
  Build(x->RS = ++CntN, Mid + 1, R);
}
signed main() {
  Build(N, 1, 50000);
  n = RD();
  for (unsigned i(1); i <= n; ++i) {
    scanf("%s", IO);
    if (*IO == 'P') S[++Cnt].Inp(), N->Insert(1, 50000, S + Cnt);
    else A = RD(), Ans = 0, N->Find(1, 50000), printf("%d\n", (int)(Ans / 100));
  }
  return Wild_Donkey;
}