无脑秒斜率李超树 _区间

文章目录三.板题（ [[]Blue Mary开公司]()）五.高端操作四.ZZH的旅行Ｔｈａｎｋｓ！
一.What？
李超树个人认为用处有点大，因为会了李超树，就再也不怕斜率优化做不出来了，你但凡能够推出一个一次函数的式子那铁定用李超树。所以撒子是李超树呀？就是变异的线段树，即在某个区间内维护区间中点值最大的一条线段，然后查询就是问某个点的最大值，直接一一映射到区间中就行了。所以插入 O ( log ? n 2 ) O(\log n^2) O(logn2)（常数巨?。?，查询 O ( log ? n ) O(\log n) O(logn) 。
二.How？
这里就口胡口胡。
1.插入（）
step1：
首先根据我们的定义，每个区间要保留中点值最大的一条线，所以将老线段的中点值跟新线端的中点值比较取大的一个。如果老线段的中点值要小一些就跟新线端swap一下，保证新线端中点值更小。

文章插图
step2：
考虑下传，有这样两种情况：
①新线端的斜率较?。?
可以看到，mid右面新线段被吊打，然而左边就不一定了，所以要更新左边。
②新线端斜率更大
可以看到，ｍｉｄ左面新线段被吊打，然而右边就不一定了，所以要更新右边。

文章插图
Code：

inline void update (int Index, int l, int r, int now){int mid = l + r >> 1;if (w (now, mid) > w (t[Index], mid))swap (now, t[Index]);if (l < r){if (k[t[Index]] > k[now])update (Index * 2, l, mid, now);elseupdate (Index * 2 + 1, mid + 1, r, now);}}

2.查询（query）
显而易见，将当前区间存的线段的答案值跟子区间的答案值比较就行。

inline double query (int Index, int l, int r, int now){if (l == r){return w (t[Index], now);}int mid = l + r >> 1;if (mid >= now){return max (w (t[Index], now), query (Index * 2, l, mid, now));}else{return max (w (t[Index], now), query (Index * 2 + 1, mid + 1, r, now));}}

三.板题（ []Blue Mary开公司）
注意横截距为1，要减哟！
【无脑秒斜率李超树】

#include using namespace std;#define M 50005#define N 100005#define LL long longint q, n;double k[N], b[N];inline int read (){int x = 0, f = 1; char c = getchar ();while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar ();}while (c >= '0' && c <= '9') {x = x * 10 + c - 48; c = getchar ();}return f * x;}inline double w (int id, int pos){return k[id] * (pos - 1.0) + b[id];}struct Segemetree {int t[M * 4];inline void update (int Index, int l, int r, int now){int mid = l + r >> 1;if (w (now, mid) > w (t[Index], mid))swap (now, t[Index]);if (l < r){if (k[t[Index]] > k[now])update (Index * 2, l, mid, now);elseupdate (Index * 2 + 1, mid + 1, r, now);}}inline double query (int Index, int l, int r, int now){if (l == r)

无脑秒斜率 李超树

无脑秒斜率李超树