线段树另一半家桶

前一半家桶

常年做数据结构的人都目光呆滞，极度自卑，后面忘了。

线段树分裂

就是裂开，咋合的就咋裂开,进而和线段树合并类似地，这个东西用于权值线段树的操作。然后线段树合并和线段树分裂一般同时出现，空间炸炸的，这个时候就要写垃圾桶，就是把没用的节点编号扔到一个栈里头。

板

	inline int merge(int x,int y,int l,int r){
		if(!x||!y)return x^y;
		if(l==r){
			tree[x].val+=tree[y].val;
			del(y);
			return x;
		}
		int mid=l+r>>1;
		ls(x)=merge(ls(x),ls(y),l,mid);
		rs(x)=merge(rs(x),rs(y),mid+1,r);
		push_up(x);
		del(y);
		return x;
	}
	inline void split(int &x,int &y,int l,int r,int ul,int ur){
		if(r<ul||l>ur)return ;
		if(!x)return ;
		if(l>=ul&&r<=ur){
			y=x;
			x=0;
			return ;
		}
		if(!y)y=newnode();
		int mid=l+r>>1;
		if(ul<=mid)split(ls(x),ls(y),l,mid,ul,ur);
		if(ur>mid)split(rs(x),rs(y),mid+1,r,ul,ur);
		push_up(x);
		push_up(y);
	}

码长这个样子，就是说从 \(x\) 树中裂出一个值域为 \([l,r]\) 的小树 \(y\)，每次遇到小树范围内的节点就给它抢过来（y=x,x=0）。

这个题就是说每个multiset就是一个 \(rt\)，然后你分分合合一下。

排序

就是说一个升降序段就是一个权值线段树，每次排序可能会撞到之前排好序的位置，这个时候就拿set维护一下排好序的区间端点然后直接找，找完分裂。

CF911G

这个还挺一眼的，发现 \(a_i\) 特别小所以直接开100个线段树维护数组下标，每次把 \(x\) 线段树的 \([l,r]\) 下标分裂后合并到 \(y\) 线段树上。

线段树优化建图

普遍是容易的。

CF786B

板。

炸弹

处理出每个蛋能影响到的区间，线段树优化连边，然后发现会成环所以跑塔尖缩点。有个假做法是在这张dag上跑计数dp，然而一个点可能有多个出边并在之后汇合到一点，考虑到一个蛋最终能影响到的一定是一个连续段的形式，转而维护scc间能覆盖的最左最右位置即可，这样是可以跑拓扑序bfs的。

PUS

跑一个差分约束，\(u>v =u\rightarrow v\) 有环无解，无环为最短路。

但是这里的连边是一坨连向一坨形式的，此时有一个trick就是超级节点，就是开一个新节点 \(p\) 使得边集 \(E=\{(u_i,v_j,w)\}\) 变成 \(E'=\{(u_i,p,w)\}\cup\{(p,v_i,w)\}\) 这样边数就从 \(O(n^2)\) 变成 \(O(n)\) 了，然后分别开出入边线段树优化建图（但是这个题一边的点特别少，所以可以开一个线段树，少的暴力连边）。

线段树分治

这一段先跳过，因为学校oj的cf炸了。

线段树二分

线段树长得就很二分，这样可以把一些看起来唐唐的 \(O(nlog^2n)\) 变成看起来牛牛的 \(O(nlogn)\)。但是这块没啥题。

Siano

有一个容易得到但是我没得到的性质就是说长得快的在一个切割的时间段一定不低，可以分讨一下 \(a_j>a_i\)，如果 \(ij\) 都切了那就是一样高，\(j\) 切了 \(i\) 没切那肯定 \(j=b,i\le b\)，\(i\) 切了 \(j\) 没切是不存在的，能发生这种情况说明 \(j\) 先前被砍到了一个以它的速度不能弥补的高度差（并且j更矮），但是 \(j\) 是一定长的快的，所以那一次 \(i\) 也一定被砍了，所以就有问题了。

这样的话按生长速度重排一下。每次先打一个生长tag，这样一定有一个后缀(前缀)段是一起高于\(b\) 的，二分出这个段然后贡献，覆盖即可。

永无乡

这不是我们线段树合并的梗吗。确实没太明白哪要二分，可能是kth吧，总之很牵强。