P3081 [USACO13MAR] Hill Walk G

原题面：Luogu

知识点：扫描线，李超树。

被离散化鲨了哈哈，一个人交了三页半，感谢大神的提交记录救我一命呜呜：https://www.luogu.com.cn/record/123948215。

简述

给定平面坐标系上的 \(n\) 条线段，每条线段的两个端点为 \((x_1, y_1)\)，\((x_2, y_2)\) 且满足 \(x_1<x_2\)，\(y_1<y_2\)，且有且仅有第一条线段满足 \((x_1, y_1) = (0,0)\)。
每条线段都代表一座山。初始时一个人位于 \((0, 0)\) 并在第一座山开始向右攀登，最右端 \((x_2, y_2)\) 是山的边缘，他会在边缘进行一个信仰之跃向下跳到横坐标为 \(x_2\) 位置并尝试降落到其他山上的非边缘位置，若降落到另一座山上则会继续在新的山上进行攀登，否则就摔似了（悲
求这个人似之前攀登过了多少座山。
\(1\le n\le 10^5\)，\(0\le x_1<x_2\le 10^9\)，\(0\le y_1<y_2\le 10^9\)。
1S，125MB。

分析

初始时位于第一条线段上，考虑模拟攀登的过程，在边缘向下跳到最高的山上等价于找与 \(x = x_2\) 交点纵坐标最大的线段，考虑使用李超树加入寻找后继的过程。但是要保证要找的线段可以降落到达，而李超树不支持删除操作，不能在一开始就将所有线段插入并仅在要查询降落到的下一座山时将不能到达的删除，则考虑使用扫描线在查询时先仅将对此时有贡献的插入。

设当前位于的线段为 \((x_1, y_1)\rightarrow (x_2, y_2)\)，则可能成为当前线段后继的线段 \((x_1', y_1')\rightarrow (x_2', y_2')\) 一定满足 \(x_1'\le x_1\)，\(x_2'>x_2\) 且在 \(x=x_2\) 处交点坐标不大于 \(y_2\)。如果先将所有线段按左端点 \(x_1'\) 进行排序然后依次枚举，则这些线段一定是连续的一段区间，考虑按照上述限制枚举这段区间并将每条线段插入到李超树区间 \([x_1', x_2'-1]\) 中，查询 \(x=x_2\) 处即可得到后继，经过的山数量加一，若不存在则停止。

横坐标范围比较大注意先离散化再插入到李超树中。但需要注意如果仅把所有线段的横坐标离散化并直接替换原线段，可能会导致新的线段间出现相交的情况，因为只离散化横坐标后计算线段的斜率，相当于直接把一段很长的区间缩没了，这么搞显然不行。我的解决方案是仅在将线段插入李超树使用离散化后的横坐标表示区间，在计算线段某点的值时仍使用原始的横坐标。

总时间复杂度 \(O(n\log^2 n)\) 级别。

代码

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define pr std::pair
#define mp std::make_pair
const int kN = 1e5 + 10;
const int kX = kN << 2;
const double eps = 1e-9;
const double kInf = 1e18 + 2077;
//=============================================================
struct Line {
  LL x1, y1, x2, y2;
  int l, r, p;
  double k, b;
} l[kN];
int n, linenum;
int datanum, data[kN << 2];
int now, nowp, nowh, ans;
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
int cmp(double x_, double y_) {
  if (x_ - y_ > eps) return 1;
  if (y_ - x_ > eps) return -1;
  return 0;
}
double calc(int id_, int x_) {
  double ret = l[id_].b + l[id_].k * x_;
  return ret;
}
void Add(int x0_, int y0_, int x1_, int y1_) {
  ++ linenum;
  if (x0_ == x1_) {
    l[linenum].k = 0;
    l[linenum].b = 1.0 * std::min(y0_, y1_);
  } else{
    l[linenum].k = 1.0 * (y1_ - y0_) / (x1_ - x0_);
    l[linenum].b = y0_ - l[linenum].k * x0_;
  }
}
bool cmp1(Line fir_, Line sec_) {
  if (fir_.x1 != sec_.x1) return fir_.x1 < sec_.x1;
  return fir_.y2 > sec_.y2;
}
namespace LSeg {
  #define ls (now_<<1)
  #define rs (now_<<1|1)
  #define mid ((L_+R_)>>1)
  const int kNode = kX << 3;
  int t[kNode];
  void Update(int now_, int L_, int R_, int u_) {
    int& v_ = t[now_];
    int bmid = cmp(calc(u_, data[mid]), calc(v_, data[mid]));
    if (bmid == 1 || (!bmid && u_ < v_)) std::swap(u_, v_);
    int bl = cmp(calc(u_, data[L_]), calc(v_, data[L_]));
    int br = cmp(calc(u_, data[R_]), calc(v_, data[R_]));
    if (bl == 1 || (!bl && u_ < v_)) Update(ls, L_, mid, u_);
    if (br == 1 || (!br && u_ < v_)) Update(rs, mid + 1, R_, u_);
  }
  void Modify(int now_, int L_, int R_, int l_, int r_, int u_) {
    if (l_ <= L_ && R_ <= r_) {
      Update(now_, L_, R_, u_);
      return ;
    }
    if (l_ <= mid) Modify(ls, L_, mid, l_, r_, u_);
    if (r_ > mid) Modify(rs, mid + 1, R_, l_, r_, u_);
  }
  pr <double, int> pmax(pr <double, int> x_, pr <double, int> y_) {
    if (cmp(x_.first, y_.first) == -1) return y_;
    if (cmp(x_.first, y_.first) == 1) return x_; 
    return x_.second < y_.second ? x_ : y_;
  }
  pr <double, int> Query(int now_, int L_, int R_, int pos_) {
    if (R_ < pos_ || pos_ < L_) return {-kInf, 0};
    double val_ = calc(t[now_], data[pos_]);
    if (L_ == R_) return mp(val_, t[now_]);
    return pmax(mp(val_, t[now_]), pmax(Query(ls, L_, mid, pos_), 
                                        Query(rs, mid + 1, R_, pos_)));
  }
  #undef ls
  #undef rs
  #undef mid
}
void Init() {
  n = read();
  for (int i = 1; i <= n; ++ i) {
    l[i].x1 = read(), l[i].y1 = read();
    l[i].x2 = read(), l[i].y2 = read();
    l[i].l = l[i].x1, l[i].p = l[i].x2, l[i].r = l[i].x2 - 1;
    data[i] = l[i].x1, data[i + n] = l[i].x2;
    data[i + 2 * n] = l[i].r;
  }
  std::sort(data + 1, data + 3 * n + 1);
  datanum = std::unique(data + 1, data + 3 * n + 1) - data - 1;
  for (int i = 1; i <= n; ++ i) {
    l[i].l = std::lower_bound(data + 1, data + datanum + 1, l[i].l) - data;
    l[i].r = std::lower_bound(data + 1, data + datanum + 1, l[i].r) - data;
    l[i].p = std::lower_bound(data + 1, data + datanum + 1, l[i].p) - data;
  }
  std::sort(l + 2, l + n + 1, cmp1);
  for (int i = 1; i <= n; ++ i) {
    Add(l[i].x1, l[i].y1, l[i].x2, l[i].y2);
  }

  l[0].b = -kInf;
}
//=============================================================
int main() {
  // freopen("3.txt", "r", stdin);
  // freopen("2.txt", "r", stdin);
  Init();
  ans = 1;
  now = 1, nowp = l[1].x2, nowh = l[1].y2;
  
  for (int i = 2; ; ) {
    for (; i <= n; ++ i) {
      if (l[i].x1 > nowp) break;
      if (l[i].x2 <= nowp || calc(i, nowp) > nowh) continue;
      LSeg::Modify(1, 1, datanum, l[i].l, l[i].r, i);
    }
    int ret = LSeg::Query(1, 1, datanum, l[now].p).second;
    if (!ret) break;
    ++ ans;
    now = ret, nowp = l[now].x2, nowh = l[now].y2;
  }
  printf("%d\n", ans);
  return 0;
}