Tips区间修改的多次建树记得每个区间的add都清空！

线段树核心的题目复杂度一般是nlogn

设计算法的时候，第一维循环n一般是枚举我们建树的数组，可以像是枚举区间左端点之类的

第二层的话一般需要做到用线段树log维护枚举位置变动的贡献，这个贡献区间往往和pre,nxt挂钩

---------------------------------------------------------------------------------------------------

第一道例题：BZOJ3747

1e6个色块，每种颜色有权重，选一个区间使得色块贡献最大，区间只出现一次的颜色才计入贡献

n=9,m=4,color=[2,3,1,1,4,1,2,4,1],w=[5,3,6,6],ans=15

这个题尝试考虑枚举左端点，那么我们就要尝试维护区间最大值来决策区间右端点

作为边界，我们首先左端点在1，这时要想得到右端点的最优，那么就要把所有颜色出现的第一次区间都更新贡献，

因为左端点在1那么必然每种颜色只有把[i,nxt[i]-1]这段位置作为右端点才能得到贡献。

这样我们就处理好了边界。

接下来考虑左端点右移一位，[i-1,nxt[i-1]-1]这段区间作为右端点就要减去i-1那个色块的贡献，

而若nxt[i-1]存在，那么[nxt[i-1],nxt[nxt[i-1]]-1]这段区间内的右端点又会获得nxt[i-1]的贡献。

有了上面的基础写出枚举右端点的也很轻松了

枚举右端点的思路更自然，不需要做预处理，扫到哪更新到哪

---------------------------------------------------------------------------------------------------

第二道例题：HDU6070

6e4长度的数列，要求一个区间使得(区间数字种类/区间长度)最小

去年的多校题，套用上面那题抽象出来的模型写了一份，比当初抄题解AC爽多了，

当初写的枚举右端点，这次写的枚举左端点，维护公式最大值。与上一题不同之处在于左端点贡献范围。

---------------------------------------------------------------------------------------------------

第三道例题：cf834D

分k段让各段中不同数字的个数最大

这个属于线段树优化DP了，目前接触不多，可能之后会调整文本位置

满足最优子结构,dp

设计状态dp[n][k]表示前n个元素划分k段的最优值,由于k一定从k-1跑出来，

所以第一维循环一定是枚举k，接着就要往第二维选择哪一个k号区间的开头寻求突破

先写出一个暴力版本的转移方程：dp[i][j]=max(dp[k][j-1] + val(k+1,i))

我们要做的就是找到这个最优的k，这里如果发现了新加入端点的贡献是到pre都加1，并且见过重复建树的操作应该就好做了。

用dp数组初始化线段树的操作挺新颖的，和第二题中维护公式变形一样，

需要观察到贡献，最值之间的关系，但凡涉及最值，不妨往线段树上思考，通过公式的变形维护合理的信息，寻找最优的端点

 

---------------------------------------------------------------------------------------------------

第四道例题:cf Trains and Statistic

x轴每个点可以跳到[i+1,a[i]]，问p(i,j)之和，表示i到j最少跳跃次数，1e5个点

最优子结构比较好想，因为每个点都能访问后面所有的点，

dp[i]表示i出发最优访问后面所有点的距离和

首先dp[i]初值有a[i]-i，这些是一步跳到的点

在a[i]右边的点，我们肯定要在i+1到a[i]里选一个点（最短距离2个不优）作为跳板才能到达

体感是那个能跳的最远的点可以有最好的策略，因为它的可选路径必然括了所有其他点的最优路径，

他可以跳到所有其他点1步能到的地方，还能花1步到其他点至少2步的地方

---------------------------------------------------------------------------------------------------

第五道例题:629D - Babaei and Birthday Cake

在两维约束下的dp转移

这种应该是标准的线段树优化dp？通过按时间加入点满足第一个维度，

在第二维上建线段树，还未出现的点初始化为不影响答案的值，例如0

保证了在第二维查询到的点都是在这个点之前出现的点