A.染色
B.字符串
求一个字符串所有本质不同子串的本质不同子串数之和。
事实上跟 区间本质不同子串个数 差不多，等回头补。
C.前缀和
区间所有子区间最大值的和，但是强制在线。
题解说把历史和线段树可持久化一下就好了，不会。
不如考虑单调栈预处理出一个数左边第一个比他大的数的坐标和右边第一个比他大的数的坐标，我们可以看成一条线段。
这样对于一次查询 \(l,r\)，被完全包含的线段贡献非常好算，跨左区间或右区间或同时跨左右区间的线段贡献通过预处理也可以 \(O(1)\) 算，然后就做完了。