(参考https://blog.csdn.net/zearot/article/details/48299459以及Clove_unique的csdn博客)
线段树应用场景是需要符合区间加法信息的，我就来做https://blog.csdn.net/zearot/article/details/48299459这篇文章中的几道题来试试看吧。
主要理清楚要维护区间信息，让区间信息符合区间加法的性质
零.逆序对
逆序对属于二维偏序中的特例，指的是一个序列a1,a2,a3...aN，求出满足：ai > aj 且 i < j 的个数的一系列问题。
493. 翻转对
这也是一道逆序对的问题
线段树常见思想，1维排序，然后第二维进行插入，用线段树进行统计。
cpp：
java：
一.染色问题
hdu1556
code:https://paste.ubuntu.com/p/RSPfvr6Z7t/
询问最后每个点有几种颜色
hdu5203
code:https://paste.ubuntu.com/p/t9FSzwtVbC/
询问区间的颜色
二.基本线段树题目
1.ural1989
字符串单点更新，询问是否有回文串。
询问是否是回文串，我们需要统计hash值来判断是否回文串。
区间信息: 字符串的hash值
code:https://paste.ubuntu.com/p/cpCc36RVFf/
- poj3667
这道题写了很久，错了很久，是一道区间合并的题。
寻找最左边的一个线段，分3种情况，可能出现在节点的左边，也可能出现在中间或者右边，所以我们需要通过线段树维护 从左边的最长和从右边的最长，以及区间最长3个值。
当左儿子节点区间最长能满足的时候，往左儿子走，在中间的情况，我们需要统计左儿子的从右边最长以及右儿子的左边最长，最次，往右儿子方向走。
这道题需要两种标记。
code: https://paste.ubuntu.com/p/YZHHgnRs5S/
3.Codeforces 527C Glass Carving
和上面一道差不多，也是区间合并的问题，更简单些，是单点更新，统计有多少个连续的0(不妨设),还是分为三部分来处理，使用两个线段树来统计最后结果是(sx[1][0]+1)*(sx[1][1]+1)
code:https://paste.ubuntu.com/p/M7kKzSM6TN/
4.hdu3016 Man Down
5.Codeforces 558E A Simple Task
6.hdu2795
网友评论