do_while_true @ 2022-06-26 23:03:31
今年的早些时候，年轻的 dwt（do_while_true） 正照常水群。
他看见 LA 群里强大的 George1123 正在吐槽早些时候写的臃肿题解，举了李超树的例子。
dwt 定睛一看，怎么李超树还有如此简洁的写法？他翻了 oi-wiki，翻了洛谷题解区，竟然都是 dwt 年少懵懂时所写的巨型分类讨论：
举例（来自我 21 年 4 月的提交记录）：
void modify(int x, int cl, int cr, int l, int r, int u) {
int v = tree[x].s, mid = (cl + cr) >> 1;
if(r < cl || cr < l) return ;
ld yu = calc(u, mid), yv = calc(v, mid);
if(l <= cl && cr <= r) {
if(cl == cr) {
if(yu > yv) tree[x].s = u;
return ;
}
if(li[v].k < li[u].k) {
if(yu > yv) {
tree[x].s = u;
modify(ls, cl, mid, l, r, v);
}
else modify(rs, mid+1, cr, l, r, u);
}
else if(li[v].k > li[u].k) {
if(yu > yv) {
tree[x].s = u;
modify(rs, mid+1, cr, l, r, v);
}
else modify(ls, cl, mid, l, r, u);
}
else if(li[u].b > li[v].b) tree[x].s = u;
return ;
}
modify(ls, cl, mid, l, r, u);
modify(rs, mid+1, cr, l, r, u);
}他从未发现李超树竟然如此好写，于是费尽千辛万苦学会了李超树的简洁写法，现在它已经全面上线 oi-wiki，欢迎大家来学习和交流！
by cnyzz @ 2022-06-27 07:39:41
我的（购票）：
ll calc(int id,int x) {return 1ll*a[id]*x+b[id];}
void update(int &p,int l,int r,int id) {
if(!p) return t[p=++tot]=id,void();
int mid=(l+r)>>1;
if(calc(id,mid)<calc(t[p],mid)) swap(t[p],id);
if(l==r) return;
if(calc(id,l)<calc(t[p],l)) update(ls[p],l,mid,id);
else if(calc(id,r)<calc(t[p],r)) update(rs[p],mid+1,r,id);
}
ll query(int p,int l,int r,int x) {
if(!p) return inf;
if(l==r) return calc(t[p],x);
int mid=(l+r)>>1;ll ret=calc(t[p],x);
if(x<=mid) ret=min(ret,query(ls[p],l,mid,x));
else ret=min(ret,query(rs[p],mid+1,r,x));
return ret;
}by Alex_Wei @ 2022-06-27 08:05:24
const int N = 1e5 + 5;
double k[N], b[N];
double get(int x, int id) {return k[id] * x + b[id];}
void modify(int l, int r, int x, int v) {
int m = l + r >> 1;
if(get(m, v) > get(m, mx[x])) swap(mx[x], v);
if(get(l, v) > get(l, mx[x])) modify(l, m, x << 1, v);
if(get(r, v) > get(r, mx[x])) modify(m + 1, r, x << 1 | 1, v);
}
double query(int l, int r, int p, int x) {
double ans = get(p, mx[x]);
if(l == r) return ans;
int m = l + r >> 1;
if(p <= m) return max(ans, query(l, m, p, x << 1));
return max(ans, query(m + 1, r, p, x << 1 | 1));
}这个 modify 整齐，好写，容易理解！！！！
by Alex_Wei @ 2022-06-27 08:06:07
哦原来您就是这么写的，那没事了！
by Alex_Wei @ 2022-06-27 08:06:47
我花了好长时间钻研李超树最后得到了这样一个 modify 函数！
by do_while_true @ 2022-06-27 16:37:17
@Alex_Wei 哈哈哈哈我也受到了很多您的启发，您的博客写的真的非常好！受益颇深！
by Cat_shao @ 2022-08-05 06:54:26
@do_while_true 您假了
https://www.luogu.com.cn/discuss/471593
第二组是卡oi-wiki上的代码。
by do_while_true @ 2022-08-05 08:48:53
@Cat_shao 感谢您！我大概改了一下现在过了所有的 hack，原因其一是 upd 没有判线段标号，其二是比较浮点数没有使用 eps 比较。
我不太懂 eps 应设为多少合适，暂且设了
#include <iostream>
#include <string>
#define MOD1 39989
#define MOD2 1000000000
#define MAXT 40000
using namespace std;
typedef pair<double, int> pdi;
const double eps=1e-9;
int cmp(double x, double y) {
if(x - y > eps) return 1;
if(y - x > eps) return -1;
return 0;
}
struct line {
double k, b;
} p[100005];
int s[160005];
int cnt;
double calc(int id, int d) { return p[id].b + p[id].k * d; }
void add(int x0, int y0, int x1, int y1) {
cnt++;
if (x0 == x1) // 特判直线斜率不存在的情况
p[cnt].k = 0, p[cnt].b = max(y0, y1);
else
p[cnt].k = 1.0 * (y1 - y0) / (x1 - x0), p[cnt].b = y0 - p[cnt].k * x0;
}
void upd(int root, int cl, int cr, int u) { // 对线段完全覆盖到的区间进行修改
int &v = s[root], mid = (cl + cr) >> 1;
if (cmp(calc(u, mid), calc(v, mid)) == 1) swap(u, v);
int bl = cmp(calc(u, cl), calc(v, cl)), br = cmp(calc(u, cr), calc(v, cr));
if (bl == 1 || (!bl && u < v))
upd(root << 1, cl, mid, u);
if (br == 1 || (!br && u < v))
upd(root << 1 | 1, mid + 1, cr, u);
}
void update(int root, int cl, int cr, int l, int r,
int u) { // 定位插入线段完全覆盖到的区间
if (l <= cl && cr <= r) {
upd(root, cl, cr, u);
return;
}
int mid = (cl + cr) >> 1;
if (l <= mid) update(root << 1, cl, mid, l, r, u);
if (mid < r) update(root << 1 | 1, mid + 1, cr, l, r, u);
}
pdi pmax(pdi x, pdi y) { // pair max函数
if (cmp(x.first, y.first) == -1)
return y;
else if (cmp(x.first, y.first) == 1)
return x;
else
return x.second < y.second ? x : y;
}
pdi query(int root, int l, int r, int d) { // 查询
if (r < d || d < l) return {0, 0};
int mid = (l + r) >> 1;
double res = calc(s[root], d);
if (l == r) return {res, s[root]};
return pmax({res, s[root]}, pmax(query(root << 1, l, mid, d),
query(root << 1 | 1, mid + 1, r, d)));
}
int main() {
ios::sync_with_stdio(false);
int n, lastans = 0;
cin >> n;
while (n--) {
int op;
cin >> op;
if (op == 1) {
int x0, y0, x1, y1;
cin >> x0 >> y0 >> x1 >> y1;
x0 = (x0 + lastans - 1 + MOD1) % MOD1 + 1,
x1 = (x1 + lastans - 1 + MOD1) % MOD1 + 1;
y0 = (y0 + lastans - 1 + MOD2) % MOD2 + 1,
y1 = (y1 + lastans - 1 + MOD2) % MOD2 + 1;
if (x0 > x1) swap(x0, x1), swap(y0, y1);
add(x0, y0, x1, y1);
update(1, 1, MOD1, x0, x1, cnt);
} else {
int x;
cin >> x;
x = (x + lastans - 1 + MOD1) % MOD1 + 1;
cout << (lastans = query(1, 1, MOD1, x).second) << endl;
}
}
return 0;
}