动态开点
前言：
有一道题，题解有两种做法，但一开始我没有往下翻，就照着第一个动态开点的方式去学，但是时间复杂度因为还有其他比较大的数据结构嵌套，所以会
正文：
其实动态开点是一个能把线段树的空间复杂度大大降低的好东西。
平常我们知道线段树开的空间是四倍所需大小的，但是有一些节点我们从头到尾都不会去访问它，那么就打打浪费空间了。比如说在一些要开 1e9 的范围时，查询修改的区间只有 2e5 个，那么我们只需要在需要这个节点访问时添加这个节点即可，空间就会被降到 2e5*log(1e9)。
比如我们加入2这个节点，就只需要建立 1至5,1至3,1至2,2这四个节点即可。
我们考虑建这样一棵树和普通的线段树的区别在哪里。答案就在编号上，我们普通的线段树当前节点的左右儿子编号就是当前节点编号乘2，然后右儿子加一。但如果我们现在还这样写就等于没有优化，空间还是会直接炸。
那么考虑按照节点的加入顺序去编号，然后每个节点多记录一下自身的左右儿子编号，这样没有扫到的空间就可以省下来了。
而查询和线段树一样，注意的是如果当前节点没有左儿子或右儿子，但要查的话直接跳过即可，毕竟没有的话就说明没有修改在这一区间，查了也没用。
板题讲解：
题目：CF915E
这道题就是一道动态开点的板子，我们可以发现他的操作区间其实很少，直接动态开点，单点就是记录当前这个区间有多少工作日，简单处理即可。
参考代码：
（写的有点丑，将就看看就可以了）
//空间要开大一点，这道题的数据可能出现问题了，开小了过不去
#include<bits/stdc++.h>
#define ls tr[p].ch[0]
#define rs tr[p].ch[1]
#define mid (ll+rr)/2
using namespace std;
struct f{int add,ch[2],sum;}tr[300005*55];//ch[0]是左儿子,ch[1]是右儿子
int cnt;
void push_down(int p,int ll,int rr){//简单懒标记下传，和线段树一样
int sum=mid-ll+1,sum1=rr-mid;
if(tr[p].add==1){tr[ls].sum=sum;tr[ls].add=1;tr[rs].sum=sum1;tr[rs].add=1;}
else {tr[ls].sum=0;tr[ls].add=2;tr[rs].sum=0;tr[rs].add=2;}
tr[p].add=0;
}
void update(int p,int l,int r,int ll,int rr){
if(ll>=l&&rr<=r){tr[p].add=1;tr[p].sum=rr-ll+1;return;}
if(!ls){tr[p].ch[0]=++cnt;}//如果没有左右儿子就加上
if(!rs){tr[p].ch[1]=++cnt;}//如果没有左右儿子就加上
if(tr[p].add) push_down(p,ll,rr);
if(l<=mid) update(ls,l,r,ll,mid);
if(r>mid) update(rs,l,r,mid+1,rr);
tr[p].sum=tr[ls].sum+tr[rs].sum;
}
void update1(int p,int l,int r,int ll,int rr){
if(ll>=l&&rr<=r){tr[p].add=2;tr[p].sum=0;return;}
if(!ls){tr[p].ch[0]=++cnt;}//如果没有左右儿子就加上
if(!rs){tr[p].ch[1]=++cnt;}//如果没有左右儿子就加上
if(tr[p].add) push_down(p,ll,rr);
if(l<=mid) update1(ls,l,r,ll,mid);
if(r>mid) update1(rs,l,r,mid+1,rr);
tr[p].sum=tr[ls].sum+tr[rs].sum;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
int n,q;cin>>n>>q;
tr[++cnt].sum=n;tr[cnt].add=1;
while(q--){
int l,r,k;cin>>l>>r>>k;
if(k==1)update1(1,l,r,1,n);
else update(1,l,r,1,n);
cout<<tr[1].sum<<'\n';
}
return 0;
}