特点
老师说，可持久化线段树一个重要的特点就是，它的询问都是单点询问...
先记这....等我做多了题目之后再补充
李超线段树
用于维护若干个一次函数的最值
核心思想就是标记永久化， 线段树每个节点维护在该区间中点取值最大的线段，查询时求一条从上到下的链上log个线段的最值。
————一位大佬FlashHu
例题
思路： 一个区间只有在绝对不可能是答案的时候才更新，否则就把原来的/插入的的区间往下递归，插入的/原来的区间就放在当前区间，这样，我们只要把合适的区间往下递归，合适的区间留下，那么对于当前区间，无论是左边还是右边，我们都能求出最优解
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX = 40000;
int n, lastans, cnt;
struct line{
double k, b;
int id;
line() {}
line(int x1, int y1, int x2, int y2, int cnt) : id(cnt) {
if(x1 == x2) k = 0, b = max(y1, y2);
else k = (double)(y2-y1)/(x2-x1), b = (double)y1-k*x1;
}
double calc(int x) {
return k*x+b;
}
}tr[MAX<<2];
bool cmp(line a, line b, int x) {//在点x处b高于a || 高度相等且b的id比a小 ->返回1
double tmp1 = a.calc(x), tmp2 = b.calc(x);
return tmp1 != tmp2 ? tmp1 < tmp2 : a.id > b.id;
}
line query(int o, int l, int r, int x) {//因为是要返回id，而不是高度，所以返回类型设为line好一些
if(l == r) return tr[o];
int mid = (l+r)>>1;
line tmp;
if(x <= mid) tmp = query(o<<1, l, mid, x);
else tmp = query(o<<1|1, mid+1, r, x);
return cmp(tr[o], tmp, x) ? tmp : tr[o];
}
void solve(int o, int l, int r, line x) { //建议手画
if(!tr[o].id) {tr[o] = x; return ;}
if(cmp(tr[o], x, l)) swap(tr[o], x);//目前tr[o]里保存的是左端点高的
if(l == r || tr[o].k == x.k) return ;//是叶子节点 或 是两条平行直线 的情况上一行考虑过了
int mid = (l+r)>>1;
double delta = (tr[o].b-x.b)/(x.k-tr[o].k);//计算交点
if(delta < l || delta > r) return ;//交点不在区间内 ->也是在cmp那行考虑过了
//我们要下传的，肯定是可能成为答案的，即tr[o]或x 的 [l, delta]或[delta, r]，其它部分就不用了
if(delta <= mid) solve(o<<1, l, mid, tr[o]), tr[o] = x;
//交点在左区间->tr[o]的delta以左可能是答案，并且我们又要保证整个区间中delta以右的答案不丢，所以tr[o] = x
else solve(o<<1|1, mid+1, r, x);//交点在右区间->x的delta以右可能是答案
}
void change(int o, int l, int r, int ql, int qr, line tmp) {
if(ql <= l && r <= qr) {solve(o, l, r, tmp); return ;}
int mid = (l+r)>>1;
if(ql <= mid) change(o<<1, l, mid, ql, qr, tmp);
if(mid < qr) change(o<<1|1, mid+1, r, ql, qr, tmp);
}
int main() {
scanf("%d",&n);
int cmd, x1, x2, y1, y2;
for(int i = 1; i <= n; i++) {
scanf("%d",&cmd);
if(cmd == 1) {
scanf("%d%d%d%d",&x1, &y1, &x2, &y2);
x1 = (x1+lastans-1)%39989+1, y1 = (y1+lastans-1)%(1000000000)+1;
x2 = (x2+lastans-1)%39989+1, y2 = (y2+lastans-1)%(1000000000)+1;
if(x1 > x2) swap(x1, x2), swap(y1, y2);
change(1, 1, MAX, x1, x2, line(x1, y1, x2, y2, ++cnt));
} else {
scanf("%d",&x1);
x1 = (x1+lastans-1)%39989+1;
lastans = query(1, 1, MAX, x1).id;
printf("%d
", lastans);
}
}
}