李超树模板 / p4097

前言

李超树是一种维护平面线段的数据结构

可以将一次函数存储至线段树中

其可以实现如下功能：

1. 在平面上增加一条线段（ O ( log ⁡ 2 n ) O(\log^2 n) O(log2n)）
2. 查询与 x = k x=k x=k 相交的线段中纵坐标最大（小）的一条 （ O ( log ⁡ n ) O(\log n) O(logn)）

不过遗憾的是，不支持已增加线段的修改、删除

其具体实现与常规线段树比较类似

通过建树获得区间的树形结构

而增添一条线段则意味着对线段的定义域进行区间修改

修改时分为 4 种情形，依次讨论即可修改成功

查询时支持单点查询，对覆盖此节点的树进行查询即可

一、题目

模板题：洛谷-p4097

二、思路及代码 1.思路

很模板的一道题，不过要注意其要求强制在线

2.代码

代码如下：

#include 
#define int long long
#define pdd pair
using namespace std;

const double eps = 1e-8;
const int mod1 = 39989;
const int mod2 = 1e9;
const int maxn = 1e5 + 5;
int n, lastans, cnt;

pdd l[maxn];
double cal(int id, int x) { return l[id].first * x + l[id].second; }
bool judge(int id1, int id2, int x) {
  double f1 = cal(id1, x), f2 = cal(id2, x);
  return fabs(f1 - f2)  id2 : f1