李超树

模板：P4097

• 先考虑插入直线
• 在每个节点存一个 \(f_i\) 表示一条直线。需要保证 \(u\) 及其祖先的 \(f\) 中有在 \(u\) 区间的中点处取得极值的那条直线。
• 考虑更新。
• 注意到一条直线完整覆盖一个区间时，它不需要下传，因为查询它的儿子时必然经过它本身，也就能统计这条直线的贡献。
• 到达叶结点时直接比对并返回。
• 否则更新中点极值并考虑在中点劣的那条直线能否更新其左右儿子。
• 它们是直线，所以最多只能更新一边！
• 于是复杂度是正确的。

感觉上，它在二分找相交点。它在巧妙地维护一个凸包，利用懒标记推平一段已经不优的区间，单侧递归保证了复杂度。这个是 \(O(\log n)\) 的。

进行线段树套李超树。（本质是把一个区间拆成 \(\log\) 个区间，本质不同的小区间只有 \(O(n)\) 个，长度之和 \(n \log n\)。）然后能做，多一只拆分的 \(\log\)。

感觉，很好理解啊！但是我理解了好久，不懂。好像是不理解正确性，画个图用凸包理解似乎就好不少了。当作线段树懒标记就算了。

#include <bits/stdc++.h>
const int M = 1e5 + 5, mod = 39989, mod2 = 1e9 + 1;
const double eps = 1e-9;
using pai = std::pair<double, int>;

struct line {
  double k, b;
  double w(int x) { return k * x + b; }
} l[M];

int cnt;

void add(int x0, int y0, int x1, int y1) {
  ++cnt;
  if (x0 == x1)
    l[cnt] = {0.0, 1.0 * std::max(y0, y1)};
  else
    l[cnt].k = 1.0 * (y1 - y0) / (x1 - x0), l[cnt].b = y0 - l[cnt].k * x0;
}

double w(int i, int x) { return l[i].k * x + l[i].b; }

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

bool cmp(int i, int j, int x) {
  int c = cmp(w(i, x), w(j, x));
  if (c != 0) return c == 1 ? 1 : 0;
  return i < j;
}

pai mx(pai x, pai y) {
  int c = cmp(x.first, y.first);
  if (c != 0) return c == 1 ? x : y;
  return x.second < y.second ? x : y;
}

int s[M << 2];

void ins(int o, int l, int r, int v) { // 插入
  int &u = s[o], mid = l + r >> 1;
  if (!cmp(u, v, mid)) std::swap(u, v);
  if (!cmp(u, v, l)) ins(o << 1, l, mid, v);
  if (!cmp(u, v, r)) ins(o << 1 | 1, mid + 1, r, v);
}

void find(int o, int l, int r, int x, int y, int v) { // 找到所有子区间
  if (x <= l && r <= y) return ins(o, l, r, v), void();
  int mid = l + r >> 1;
  if (x <= mid) find(o << 1, l, mid, x, y, v);
  if (y > mid) find(o << 1 | 1, mid + 1, r, x, y, v);
}

pai qry(int o, int l, int r, int x) {
  if (l == r) return std::make_pair(w(s[o], x), s[o]);
  int mid = l + r >> 1;
  return mx(std::make_pair(w(s[o], x), s[o]), 
    x <= mid ? qry(o << 1, l, mid, x) : qry(o << 1 | 1, mid + 1, r, x));
}

int main() {
  int n, x0, y0, x1, y1, x, lans = 0;
  scanf("%d", &n);
  while (n--) {
    int op; scanf("%d", &op);
    if (op == 1) {
      scanf("%d %d %d %d", &x0, &y0, &x1, &y1);
      x0 = (x0 + lans - 1 + mod) % mod + 1;
      y0 = (y0 + lans - 1 + mod2) % mod2 + 1;
      x1 = (x1 + lans - 1 + mod) % mod + 1;
      y1 = (y1 + lans - 1 + mod2) % mod2 + 1;
      if (x0 > x1) std::swap(x0, x1), std::swap(y0, y1);
      add(x0, y0, x1, y1), find(1, 1, mod, x0, x1, cnt);
    } else {
      scanf("%d", &x);
      x = (x + lans - 1 + mod) % mod + 1;
      printf("%d\n", lans = qry(1, 1, mod, x).second);
    }
  }
  return 0;
}
/*
stupid mistakes:
  - l[i] = {x, l[i].k - x} ，算第二个参数时第一个参数还没计算完毕
*/