李超线段树学习笔记

模板传送门

从模板题就能看出来嗷，李超线段树非常牛逼。\bx

从名字中就能看出来嗷，这玩意儿是个线段树。

那么考虑在线段树上维护一堆线（一次函数）。

对于每个点，存所有线中，使这个线段 $ mid $ 的点的线。

对于加入一个点，根节点递归，扫到一个点时，若这个点在 $ mid $ 时大于当前最优线，就将这个线段上的最优线替换。

对于递归左右子节点，若左端点中，这个点比最优先段优，那么直接递归。否则

• 这个线不可以作为左儿子的最优线。一点也不遗憾没有递归，很好！

• 这个线可以作为左儿子的最优线。有点遗憾没有递归，但是显然这个线已经作为了这个点的最优线，从而使得无需递归。不遗憾了

右端点同理。那么这玩意儿就很合理的更新了。（动态开点）代码

void updata(int& x, int i, int L = -2e8, int R = 2e8)
{
	if (!x) x = ++idx;
	if (!id[x]) return id[x] = i, void();
	int mid = L + R >> 1;
	if (f[i](mid) > f[id[x]](mid)) swap(i, id[x]);
	if (L == R) return;
	if (f[i](L) > f[id[x]](L)) updata(l[x], i, L, mid);
	if (f[i](R) > f[id[x]](R)) updata(r[x], i, mid + 1, R);
}

对于查询，直接递归即可。全部代码

namespace LCST  //Li Chao Segment Tree
{
	struct Function
	{
		int a, b;
		int operator () (int x) { return a * x + b; }
	};
	Function f[N];
	int fidx;
	int id[N << 5];
	int l[N << 5];
	int r[N << 5];
	int idx = 1;
	int root = 1;
	void updata(int& x, int i, int L = -2e8, int R = 2e8)
	{
		if (!x) x = ++idx;
		if (!id[x]) return id[x] = i, void();
		int mid = L + R >> 1;
		if (f[i](mid) > f[id[x]](mid)) swap(i, id[x]);
		if (L == R) return;
		if (f[i](L) > f[id[x]](L)) updata(l[x], i, L, mid);
		if (f[i](R) > f[id[x]](R)) updata(r[x], i, mid + 1, R);
		return;
	}
	int query(int x, int k, int L = -2e8, int R = 2e8)
	{
		int res = 0;
		if (id[x]) res = f[id[x]](k);
		if (L == R) return res;
		int mid = L + R >> 1;
		if (k <= mid) res = max(res, query(l[x], k, L, mid));
		else res = max(res, query(r[x], k, mid + 1, R));
		return res;
	}
	inline void build()				//init
	{
		for (int i = 1; i <= idx; i++) l[i] = r[i] = id[i] = 0;
		idx = root = 1;
	}
	inline void add(int a, int b)	//add f(x)=ax+b
	{
		f[++fidx] = { a, b };
		updata(root, fidx);
	}
	inline int query(int k)			//query max f(k)
	{
		return query(1, k);
	}
}

Link-Cut-Tree学习笔记

对于一棵树，实链剖分，对每条链建立 Splay，这就是Link-Cut-Tree 的主要思想。完

Rotate(x)和Splay(x)

和普通 Splay 有一点点不一样。

inline bool isroot(int x) { return (son[fa[x]][0] != x && son[fa[x]][1] != x); }
inline void uppushdown(int x) { if (!isroot(x)) uppushdown(fa[x]); pushdown(x); }
inline bool get(int x) { return x == son[fa[x]][1]; }
inline void rotate(int x)
{
	int p = fa[x], q = fa[p]; bool chk = get(x);
	if (!isroot(p)) son[q][get(p)] = x;
	son[p][chk] = son[x][chk ^ 1];
	fa[son[x][chk ^ 1]] = p;
	son[x][chk ^ 1] = p;
	fa[p] = x, fa[x] = q;
	maintain(p), maintain(x);
}
inline void Splay(int x)
{
	uppushdown(x);
	for (int f = fa[x]; f = fa[x], !isroot(x); rotate(x)) if (!isroot(f)) rotate(get(x) == get(f) ? f : x);
}

Access(x)

使 $ x $ 与根节点在同一条实链上（且 $ x $ 为路径的尾端）

按含义模拟即可。

inline int Access(int x)
{
	for (int s = 0; x; s = x, x = fa[x])
	{
		Splay(x);
		son[x][1] = s;
		maintain(x);
	}
	return s;
}

最后的返回值为辅助树的根节点。

Makeroot(x)

使 $ x $ 作为原树的根。

先 Access(x), Splay(x)，让 $ x $ 为辅助树树的根。然后对于这条链来说，反转就是将链反转，Splay打上旋转标记即可。即reverse(x)。

或者 reverse(Access(x))，也可以，但是好像多 Splay() 能保证复杂度。

inline void makeroot(int x)
{
	Access(x), Splay(x), reverse(x);
}

Findroot(x)

找到 $ x $ 原树的根。

很普通，按含义模拟即可

inline int findroot(int x)
{
	Access(x);
	Splay(x);
	pushdown(x);
	while (son[x][0]) x = son[x][0], pushdown(x);
	Splay(x);
	return x;
}

Split(x, y)

将 $ x $ 到 $ y $ 的路径抽到一条链上。

Makeroot(x), Access(y) 就好了，再 Splay(y) 一下，$ x $ 到 $ y $ 的路径就在 $ y $ 的子树里了，操作查询直接对 $ y $ 的子树查/改即可。

inline void split(int x, int y)
{
	makeroot(x), Access(y), Splay(y);
}

Link(x, y)

连接 $ x, y $。

终于来了，连接的话 makeroot(x) 使 $ x $ 为原树和辅助树的根，然后 $ x $ 向 $ y $ 连一条虚边即可。

inline void link(int x, int y)
{
	makeroot(x);
	fa[x] = y;
}

Cut(x, y)

断开 $ x, y $ 的边。

先 Split(x, y)，这时 $ x $ 一定是 $ y $ 的左儿子，且两个点构成一颗 Splay，两点双向断开即可。

inline void cut(int x, int y)
{
	split(x, y);
	fa[x] = son[y][0] = 0;
	maintain(y);
}

总结

LCT的操作比较灵活，一般只要写的合理，跟别人写的不一样也是珂以的。