闲话
昨天晚上梦见机房里放《萤火虫从未来过》
然后切到《无梦之梦》
但是醒了还是新宝岛
果然想听歌了
哪位大佬能跟我说说饭的近况啊谢谢了
好今天一道李超树一道树上背包
我：你不是拿着系数吗怎么插出系数
lyin：你什么玩意你卷积不用点值乘
我：wssb
然而不想写拉插于是进行了一个指针释放内存的学习
旁边大佬用vector早早切掉了
我：这个玩意怎么接返回值啊
虽然最后还是切了
跑的很快（
所以我还是得给我前几天的鲜花引流
如果还没看的话可以去看看！
春風に靡く少女のように
なぜわたしたちは光がなかったの
どこまでも伸びる黒い影は
未来を見ている未来を見ている
关于李超树
李超线段树是一种用于维护平面直角坐标系内线段关系的数据结构。 - By JHSeng
你需要在线地支持 \(n\) 次两种操作：
- 加入一条定义域为 \([l, r]\) 的线段 \(l : y = kx + b\)
- 查询所有与 \(x = k\) （\(k\) 为整数）相交线段中纵坐标最大的线段的编号。若有多条输出编号最小者。
\(n ,l,r,k\le 1e5\)。
于是我们需要用到李超树来维护线段信息。
李超树是一种线段树，节点 \([l,r]\) 上维护的是该段区间上的优势线段，即在该段区间中点上取值最大的线段。询问时一层层地递归，取路径上优势线段的最大值为答案。
容易发现这样能够保证答案正确。因此李超树实际上是一棵标记永久化思想的线段树。
对于修改，我们查询到当前修改线段定义域完全包含的区间族，对于每个区间进行如下操作：
- 若该区间无优势线段，则更新该区间的优势线段为当前线段。
- 若该区间存在优势线段，分类讨论。
- 若该区间优势线段完全覆盖了当前线段，则直接返回。
- 若该区间优势线段被当前线段完全覆盖，则更新优势线段为当前线段并直接返回。
- 若该区间优势线段与当前线段在该区间内有交，则首先更新区间优势线段，并把更劣的线段递归地下传到子区间内。
由于该部分需要递归，因此更新一段区间的时间复杂度为 \(O(\log n)\)。
若每次修改的是一段线段，则其共会修改 \(O(\log n)\) 个区间，因此维护线段的李超树更新总复杂度为 \(O(\log^2 n)\)。
若每次修改的是一条直线，则其只会更新根节点，因此维护直线的李超树更新总复杂度为 \(O(\log n)\)。
对于查询，按照正常线段树进行即可。复杂度 \(O(\log n)\)。
code
#define rep(i,a,b) for (register int i = (a), i##_ = (b) + 1; i < i##_; ++i)
#define pre(i,a,b) for (register int i = (a), i##_ = (b) - 1; i > i##_; --i)
const int N = 1e6 + 10, mod1 = 39989, mod2 = 1e9;
const double eps = 1e-9;
using pdi = pair<double, int>;
int n, typ, t1, t2, t3, t4, lans;
int cnt;
struct line {
double k, b;
} p[N];
void addl(int x_0, int y_0, int x_1, int y_1){
++ cnt;
if (x_0 == x_1) p[cnt] = {0, max(y_0, y_1)};
else p[cnt].k = 1.0 * (y_1 - y_0) / (x_1 - x_0), p[cnt].b = y_0 - p[cnt].k * x_0;
}
double calc(int id, int x) {
return p[id].k * x + p[id].b;
}
int cmp(double x, double y){
if (x - y > eps) return 1;
if (y - x > eps) return -1;
return 0;
}
struct SegmentNeon {
int id;
#define ls (p << 1)
#define rs (p << 1 | 1)
#define id(p) seg[p].id
} seg[N<<2];
void __upd(int p, int l, int r, int idn) {
int mid = l + r >> 1;
if (cmp(calc(idn, mid), calc(id(p), mid)) == 1) swap(idn, id(p));
int bl = cmp(calc(idn, l), calc(id(p), l)), br = cmp(calc(idn, r), calc(id(p), r));
if (bl == 1 or (!bl and idn < id(p))) __upd(ls, l, mid, idn);
if (br == 1 or (!br and idn < id(p))) __upd(rs, mid+1, r, idn);
}
void upd(int p, int l, int r, int L, int R, int idn) {
if (L <= l and r <= R) {
__upd(p, l, r, idn);
return;
} int mid = l + r >> 1;
if (L <= mid) upd(ls, l, mid, L, R, idn);
if (mid < R) upd(rs, mid+1, r, L, R, idn);
}
pdi ckmax(pdi x, pdi y) {
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;
} template <typename ...Args> pdi ckmax(pdi x, Args... y) { return ckmax(x, ckmax(y...)); }
pdi qry(int p, int l, int r, int x) {
if (r < x or x < l) return {0, 0};
int mid = l + r >> 1;
double res = calc(id(p), x);
if(l == r) return {res, id(p)};
else return ckmax( {res, id(p)}, qry(ls, l, mid, x), qry(rs, mid+1, r, x) );
}
动态开点
平凡。
合并
两个点的两根线段取更优的一根作新点的优势线段，另一根作为新线段插入子节点中。
然后就可以搞一系列斜率优化问题了。
例题咕着，等以后水鲜花用。
标签：10,int,闲话,线段,22.10,区间,calc,id,idn From： https://www.cnblogs.com/joke3579/p/chitchat221010.html