首页 > 其他分享 >「笔记」李超线段树

「笔记」李超线段树

时间：2024-01-23 14:57:17浏览次数：35  
标签：return linenum int 线段 李超 笔记 _. now

目录

写在前面

LiChaoTree 也是 LCT（智将

和典中典之楼房重建都是\(O(\log^2 n)\) 地进行修改的样子，但是楼房重建是拆分完区间后再 \(O(\log^2 n)\) 地向上合并，这个是对拆分出的每个区间再进行拆分并做标记永久化的样子。总之都是不好合并的信息，但是前者还有办法合并，这个直接没法合并于是只能一直向下比较永久化的标记。

另外想买个眼镜厂的织姬景品我草 pdd 上便宜的一批，但是帝皇的价格基本是织姬的三倍了，这么烫啊哈哈傻逼二次元

引入

P4097 【模板】李超线段树 / [HEOI2013] Segment

要求在平面直角坐标系下维护 \(n\) 个操作，每种操作都是如下两种之一：

  • 在平面上加入一条两端点为 \((x_0,y_0)\)，\((x_1,y_1)\) 的线段，第 \(i\) 条被插入的线段的编号为 \(i\)。
  • 给定整数 \(k\)，询问与直线 \(x = k\) 相交的线段中，交点纵坐标最大的线段的编号（若有多条线段与查询直线的交点纵坐标都是最大的，则输出编号最小的线段）。若不存在线段与给定直线相交输出 \(0\)。

\(1 \le n \le 10^5\)，\(1 \le k, x_0, x_1 \le 39989\)，\(1 \le y_0, y_1 \le 10^9\)。
强制在线。
1S，128MB。

区间修改，单点查询，首先想到用线段树处理。

称某条线段 \(i\) 支配某个区间 \([L, R]\)，当且仅当 \(\forall L\le x\le R\)，与直线 \(x=k\) 相交的线段中交点纵坐标最大的线段为 \(i\)。令线段树维护区间的支配线段，查询则递归至 \([k,k]\) 并输出。

然而常规的线段树不好维护，对于某个区间可能不存在支配线段从而无法合并区间；两条覆盖了同一区间的线段，可能会出现在区间的两端最优的线段不同的情况，于是也没法给区间直接打懒标记代替修改。

于是李超线段树出现了。它通过分析线段相交的性质避免了许多重复的修改，并通过标记永久化解决了难以合并的问题，使得可以在 \(O(\log^2 n)\) 的时间复杂度内完成区间修改操作。

线段

为了方便求线段与 \(x=k\) 的交点，先将所有线段表示为 \(y=k\times x + b\) 的形式。钦定 \(y_0<y_1\)，则有：

  • \(x_0=x_1\) 时，有：\(y=0\times x + \max(y_0, y_1)\)。
  • \(x_0\not= x_1\) 时，有：\(k = \frac{y_1-y_0}{x_1-x_0}\)，\(b = y_0-k\times x_0\)。
struct Line {
  double k, b;
} l[kN];
int linenum;

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_) { //计算 x=x_ 与线段 id_ 交点的纵坐标
  return l[id_].b + l[id_].k * x_;
}
void Add(int x0_, int y0_, int x1_, int y1_) {
  ++ linenum;
  if (x0_ == x1_) {
    l[linenum] = (Line) {0, 1.0 * std::max(y0_, y1_)}; //特判斜率不存在的情况
  } else{
    l[linenum].k = 1.0 * (y1_ - y0_) / (x1_ - x0_);
    l[linenum].b = y0_ - l[linenum].k * x0_;
  }
}

区间修改

令线段树维护支配区间的线段的编号，然后考虑区间修改对其的影响。对于线段 \((x_0, y_0)\rightarrow (x_1, y_1)\)，先对其完整覆盖的线段树区间进行拆分，然后考虑对这些区间进行修改。由于标记不能合并所以无法直接打标记，只能在这些区间里继续递归并修改所有受影响的区间，考虑新的线段与之前支配该区间的线段的关系：

上面是来自 OI-wiki 的一张图，发现区间可以被新的线段与之前支配该区间的线段的交点分成两个子区间，两者分别支配两个区间，则可以直接修改新线段支配的区间，再递归对另一方进行修改，则至多向下递归 \(O(\log n)\) 次，复杂度有了保证。

然后考虑具体怎么进行上述过程：

  • 设当前区间的中点为 \(m\)，先比较新线段 \(f\) 原最优线段 \(g\) 区间中点处的值。若新线段 \(f\) 更优，则将 \(f\) 和 \(g\) 交换。
  • 然后考虑中点处 \(f\) 不如 \(g\) 优的情况：
    • 在左端点处 \(f\) 更优：则 \(f\) 和 \(g\) 在左半区间中产生了交点，\(f\) 只有在左区间才可能优于 \(g\)。则向左儿子中递归修改。
    • 在右端点处 \(f\) 更优，则 \(f\) 和 \(g\) 在右半区间中产生了交点，\(f\) 只有在右区间才可能优于 \(g\)，则向左儿子中递归修改。
    • 在左右端点处 \(g\) 都更优，那么 \(f\) 不可能成为答案，不需要继续递归。
  • 另外，若 \(f\) 和 \(g\) 刚好交于中点，在程序实现时可以归入中点处 \(f\) 不如 \(g\) 优的情况，会往 \(f\) 更优的一个端点递归。
  • 最后将 \(g\) 作为当前区间维护的线段。
void Update(int now_, int L_, int R_, int u_) { //区间拆分后递归向下进行修改
  int& v_ = t[now_];
  int bmid = cmp(calc(u_, mid), calc(v_, mid));
  if (bmid == 1 || (!bmid && u_ < v_)) std::swap(u_, v_);
  int bl = cmp(calc(u_, L_), calc(v_, L_)), br = cmp(calc(u_, R_), calc(v_, 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 {0, 0};
  double val_ = calc(t[now_], 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_)));
}

完整代码

P4097 【模板】李超线段树 / [HEOI2013] Segment

实现时将编号为 0 的线段设为 \(y=0\times x + 0\)，即 \(x\) 轴来方便进行。

//知识点：李超树
/*
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 = 4e4 + 10;
const int mod1 = 39989;
const int mod2 = 1000000000;
const double eps = 1e-9;
//=============================================================
struct Line {
  double k, b;
} l[kN];
int linenum;
//=============================================================
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_) { //计算 x=x_ 与线段 id_ 交点的纵坐标
  return l[id_].b + l[id_].k * x_;
}
void Add(int x0_, int y0_, int x1_, int y1_) {
  ++ linenum;
  if (x0_ == x1_) {
    l[linenum] = (Line) {0, 1.0 * std::max(y0_, y1_)}; //特判斜率不存在的情况
  } else{
    l[linenum].k = 1.0 * (y1_ - y0_) / (x1_ - x0_);
    l[linenum].b = y0_ - l[linenum].k * x0_;
  }
}
namespace LSeg {
  #define ls (now_<<1)
  #define rs (now_<<1|1)
  #define mid ((L_+R_)>>1)
  const int kNode = kX << 2;
  int t[kNode];
  void Update(int now_, int L_, int R_, int u_) { //区间拆分后递归向下进行修改
    int& v_ = t[now_];
    int bmid = cmp(calc(u_, mid), calc(v_, mid));
    if (bmid == 1 || (!bmid && u_ < v_)) std::swap(u_, v_);
    int bl = cmp(calc(u_, L_), calc(v_, L_)), br = cmp(calc(u_, R_), calc(v_, R_));
    if (bl == 1 || (!bl && u_ < v_)) Update(ls, L_, mid, u_); //两个 if 只会成立一个
    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 {0, 0};
    double val_ = calc(t[now_], 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
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int n = read();
  LL ans = 0;
  while (n --) {
    int opt = read();
    if (opt == 1) {
      int x0 = read(), y0 = read(), x1 = read(), y1 = read();
      x0 = (x0 + ans - 1 + mod1) % mod1 + 1,
      x1 = (x1 + ans - 1 + mod1) % mod1 + 1;
      y0 = (y0 + ans - 1 + mod2) % mod2 + 1,
      y1 = (y1 + ans - 1 + mod2) % mod2 + 1;
      if (x0 > x1) std::swap(x0, x1), std::swap(y0, y1);
      Add(x0, y0, x1, y1);
      LSeg::Modify(1, 1, mod1, x0, x1, linenum);
    } else {
      int x = read();
      x = (x + ans - 1 + mod1) % mod1 + 1;
      printf("%d\n", ans = LSeg::Query(1, 1, mod1, x).second);
    }
  }
  return 0;
}

例题

P4254 [JSOI2008] Blue Mary 开公司

给定 \(n\) 个操作，每个操作都是下列两种形式之一：

  • 给定实数 \(s,p\)，表示新增一个首项为 \(s\)，公差为 \(p\) 的等差数列。
  • 给定整数 \(t\)，询问所有等差数列的第 \(t\) 项中最大的值 \(v\)，输出 \(\max\left\{\left\lfloor\frac{v}{100}\right\rfloor, 0\right\}\)。

\(1\le n\le 10^5\)，\(1\le t\le 5\times 10^4\)，\(0< p<100\)，\(|s|\le 10^5\)。
1S，125MB。

知识点：李超树。

板题，等差数列可看做 \(y = s + p\times (x - 1)\)。

因为答案不小于 0，可以直接令 l[0].b = 0，即钦定李超树中求计算没有被线段覆盖的点的纵坐标为 0。

//
/*
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 = 5e4 + 10;
const int X = 5e4;
const double eps = 1e-9;
//=============================================================
struct Line {
  double k, b;
} l[kN];
int linenum;
//=============================================================
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_) {
  return l[id_].b + l[id_].k * x_;
}
void Add(int x0_, double y0_, int x1_, double y1_) {
  ++ linenum;
  if (x0_ == x1_) {
    l[linenum] = (Line) {0, 1.0 * std::max(y0_, y1_)};
  } else{
    l[linenum].k = 1.0 * (y1_ - y0_) / (x1_ - x0_);
    l[linenum].b = y0_ - l[linenum].k * x0_;
  }
}
namespace LSeg {
  #define ls (now_<<1)
  #define rs (now_<<1|1)
  #define mid ((L_+R_)>>1)
  const int kNode = kX << 2;
  int t[kNode];
  void Update(int now_, int L_, int R_, int u_) {
    int& v_ = t[now_];
    int bmid = cmp(calc(u_, mid), calc(v_, mid));
    if (bmid == 1 || (!bmid && u_ < v_)) std::swap(u_, v_);
    int bl = cmp(calc(u_, L_), calc(v_, L_)), br = cmp(calc(u_, R_), calc(v_, 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 {0, 0};
    double val_ = calc(t[now_], 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
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int n = read();
  while (n --) {
    char opt[20]; scanf("%s", opt + 1);
    if (opt[1] == 'P') {
      int x0 = 1, x1 = X;
      double y0, y1; scanf("%lf %lf", &y0, &y1);
      y1 = y0 + y1 * (X - 1);
      Add(x0, y0, x1, y1);
      LSeg::Modify(1, 1, X, x0, x1, linenum);
    } else {
      int x = read();
      pr <double, int> ret = LSeg::Query(1, 1, X, x);
      // printf("%lf\n", ret.first);
      // if (!ret.second) printf("0\n");
      printf("%lld\n", (LL) (ret.first / 100));
    }
  }
  return 0;
}

P3081 [USACO13MAR] Hill Walk G

给定平面坐标系上的 \(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;
}

写在最后

参考：

标签：return,linenum,int,线段,李超,笔记,_.,now
From： https://www.cnblogs.com/luckyblock/p/17982444

相关文章

  • spring学习笔记
    目录IoC概念DI(依赖注入)SpringDemo项目新建maven项目加入依赖定义类:接口和实现类Spring的配置文件Spring容器创建对象使用容器中的对象问题1:spring创建对象,调用是类的那个方法问题2:spring是在什么时候创建对象问题3:spring容器创建对象,一次创建几个获取容器中对象的信息spri......
  • QT笔记：多线程和信号槽
    QT笔记：多线程和信号槽多线程创建多线程有两种方法，一般推荐用moveToThread方法参考代码如下：mainwindow.h#ifndefMAINWINDOW_H#defineMAINWINDOW_H#include<QMainWindow>#include<QApplication>QT_BEGIN_NAMESPACEnamespaceUi{classMainWindow;}QT_END_NAMES......
  • CAN基础知识笔记
    CAN总线协议（ControllerAreaNetwork），控制器局域网总线，是德国BOSCH（博世）公司研发的一种串行通讯协议总线，它可以使用双绞线来传输信号，是世界上应用最广泛的现场总线之一。CAN通讯是异步通讯，没有时钟信号线来保持信号接收同步，是半双工通信，无法同时发送与接收，在同一时刻，只能有一个节点......
  • [SQLAlchemy] sqlAlchemy学习笔记(2): 在orm中使用select
    SELECT的作用select在sql中的作用是选中特定列并以表的形式返回,是必要的关键字;在sqlalchemy中,select()方法会返回一个Select对象,并根据这个对象引入其他方法,如where(),join(),order_by()等等fromsqlalchemyimportselectstmt=select(User).where(User.name==......
  • Kruskal 重构树学习笔记
    1.定义与构造对于一张无向图，新建\(n\)个树，原图每个点在一个树中，权值是\(0\)。按边权从小到大枚举边，如果这条边两个节点不在一棵树，合并两个节点所在的树。新建一个点，点权为加入边的边权，同时将两棵树的根节点分别设为新建点的左儿子和右儿子，将新建点设为根。实现与Kruskal最......
  • 线段树二分
    问题描述维护长度为\(n\)的序列\(a\)，支持以下操作：1ix：把\(a_i\)修改为\(x\)。2ix：询问最小的\(j\)满足\(j>=i\)且\(a_j>=x\)。\(1\leqn\leq10^6\)解决方法在线段树外直接二分可以做到\(O(n\log^2n)\)的时间复杂度，加上简单的剪枝可能效率会高一些，但都无......
  • Docker 学习笔记 - 5
    DockerFile解析是什么Dockerfile是用来构建Docker镜像的构建文件，由一系列命令和参数构成的脚本构建三步骤编写Dockerfile文件dockerbuilddockerrun文件什么样？？？熟悉的Centos为例http://hub.docker.com/_/centosDockerFile构建过程解析Dockerfile内容基础知识1、每条......
  • C++学习笔记
    C++学习笔记（1）预编译、编译、链接预编译(Preprocessing)cppreference中：GPT这么说：C++预编译是指在编译阶段之前对代码进行的一系列预处理操作。预编译的目的是为了将代码中的预处理指令和宏展开，以及进行一些其他的预处理操作。预处理指令包括以井号（#）开头的指令，如#include、#......
  • Inplementation of Binary Search Tree【1月22日学习笔记】
    点击查看代码//InplementationofBinarySearchTree#include<iostream>usingnamespacestd;structbstnode{ intdata; bstnode*left; bstnode*right;};/*bstnode*root=NULL;*//*root=NULL;wrong*//*全局范围内的变量的初始化必须在声......
  • 学习笔记438—《赤兔之死》高考满分文章
    建安二十六年，公元221年，关羽走麦城，兵败遭擒，拒降，为孙权所害。其坐骑赤兔马为孙权赐予马忠。一日，马忠上表：赤兔马绝食数日，不久将亡。孙权大惊，急访江东名士伯喜。此人乃伯乐之后，人言其精通马语。马忠引伯喜回府，至槽间，但见赤兔马伏于地，哀嘶不止。众人不解，惟伯喜知之。伯喜遣散诸人，抚其......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99