这里主要是对代码的解释
首先是对蓝书的简单做法的代码解释
我们把每一个节点看做比较独立的一个个体，他的cnt表示他所代表的区间是否在他本身的影响下被完全覆盖，这里不太好描述，下面举一个例子
比如三号节点（代表区间为[4,6]）的cnt>0表示这一段区间在他这里已经被完全覆盖了，cnt=0表示在他这里没有被完全覆盖
那么在实际中，一个单位区间如何判断他是否被覆盖？
就看从代表这个区间的叶子节点到根节点的路径上，是否存在一个节点的cnt>0
比如[4,4]这个区间，如果1,3,6,12这四个节点中有一个cnt>0那么就代表实际中，[4,4]这个区间被覆盖了
我们先不考虑长度，先单独考虑维护区间是否被覆盖，那么在这种情况下，当修改操作为+1时，线段树被划分成的若干个节点的cnt都加上1，从每一个叶子节点往上走，显然都是符合实际情况的，如果修改操作为-1，当线段树被划分成的若干个节点中的某一个节点的cnt变为0了，他所代表的这些单位区间往上走，如果某个单位区间在实际中还被覆盖，那么他一定是被之前的某一次+1操作在路径上的另一个节点覆盖的，由于操作成对出现，这个节点的-1操作肯定比+1操作后面出现，所以这个节点的cnt一定>0，所以也就不会遗漏答案，同样的分析，也不会重复计算
我们再来考虑长度，由于线段树是从下往上维护信息的，我们不妨用最暴力的方法来维护信息，假设每次修改完了之后我们都从每个单位区间向上走，走到某一个节点时，如果当前节点的cnt=0，就向上传递其子节点的len之和，如果cnt>0就传递这个区间长度，那么由我们以上分析，如果一个单位区间被记录了，那么他一定会在某一个节点（cnt>0）的时候被计算贡献，也就不会遗漏答案（这个时候其实线段树中除了根节点外的节点的len可能不是实际中的len，但是由于我们只关心根节点，根节点的len一定是实际的len，就无所谓）
我们在修改之后可以直接模拟这个过程，在某次修改中，没有被涉及的区间显然不用管，他们已经传递好了，对于涉及的区间，如果cnt被减为了0，那么我们假设从这个区间所代表的的所有单位区间向上走，由于这个区间的子树都没有被修改，所以我们不用真的走，这个区间的两个子节点的len值就是已经走完之后的len，我们直接上传两个子节点的len即可
标签：cnt,覆盖,线段,len,节点,区间,亚特兰蒂斯 From： https://www.cnblogs.com/dingxingdi/p/17913716.html