前言

好像机房人人都会这个东西，就我不会，只能爬去学一下。。。

这是啥

好像是个挺没用的东西，感觉主要处理树上数数什么的问题，都可以用 dsu 神器来替代。但也有的问题不能用 dsu 的，比如这题。

来考虑这样一件事，就是说，我们有的时候希望对于每个点都维护一棵线段树，并且希望能够实现一些鬼畜的♂操♂作♂，这时候需要用到线段树合并。

但是我们考虑这样一件事就是说，由于是合并，那么在合并之前必然是有很多的线段树，所以传统的线段树肯定是没法用的。于是——

动态开点线段树

这个东西还是比较简单的，就在插入元素的时候不采用堆式建树，而是采用记录左右儿子，然后在插入的时候访问到一个节点才会去开这个点的空间，这样就可以开下空间了。

注意一点是：动态开点的空间要开 20 倍以上，不然一开始空间会不太够。

void ins(int &i,int l,int r,int v){
	if(l>r) return;if(!i) i=++tot;
	tr[i].l=l;tr[i].r=r;
	if(l==r){tr[i].mx++;tr[i].id=l;return;}
	int mid=l+r>>1;ins(ls[i],l,mid,v);ins(rs[i],mid+1,r,v);
	pushup(i);
}

线段树合并

和 fhq 的合并差不多。

int merge(int a,int b){
	if(!a) return b;
	if(!b) return a;
	ls[a]=merge(ls[a],ls[b]);
	rs[a]=merge(rs[a],rs[b]);
	pushup(a);return a;
}

习题

我们掏出这个题单。

• P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并

发现最后只询问一次，不需要树剖，直接树上差分。但是发现需要维护很多不同的颜色，所以考虑对每个节点维护一个线段树，然后向上做的时候合并就可以了。

• P3605 [USACO17JAN]Promotion Counting P
• CF600E Lomsat gelral
• P3521 [POI2011]ROT-Tree Rotations
• CF208E Blood Cousins