线段树题集
转载自http://blog.sina.com.cn/s/blog_691ce2b7010170k7.html
线段树
zoj 1610 线段覆盖
poj 2777 线段覆盖
poj 2528 需要离散化，建树不同，需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3.
hdu 1754 求区间最大值
hdu 1166 求区间和
hdu 1698 成段更新
poj 3468 成段更新
ural 1019 覆盖加统计最长同一个颜色
zoj 2301 和上一题差不多，但是这个染色染的是点，注意染色为空的状况
poj 3264 水题，寻找区间最大最小值
poj 1151 线段树+离散化求矩形面积并
poj 1177 矩形周长并
poj 3277 求在同一水平线上的矩形面积并，按高度排序，然后变成普通线段覆盖即可。
hdu 1394 求逆序数，注意将第一个元素移到最后一个元素的逆序数变化是可以推出来的。
poj 2828 从后往前推，线段树存空位个数，查找空位即可
poj 2886 模拟约瑟夫环，跟上题类似，线段树查找第几个位置出列。
poj 2352 求x坐标有多少个已经有的星星即可。
hdu 1255 求矩形面积交，注意如何更新。
poj 3667 求区间连续值，线段树的节点域需要增加新的域T T
poj 2892 同上题，找出最大连续区间
poj 2180 同2828，插空位即可
bzoj 1230 区间异或
hdu 3911 区间异或并求区间内连续1的最多个数
zoj 3279 简单线段树。改变level的数量，询问第几个的level是多少。
hdu 3397 比较恶心，需要设计两个标记，注意传递异或和覆盖的关系，先后不一样的话结果不一样
fzu 1608 更新后，查找总区间的长度时传递
zoj 2706 讲区间值替换为平均值
poj 3368 求有序数组区间出现频率最多次数
zoj 2859 二维线段树，求矩阵部分最大值
hdu 3074 水题，求区间乘积
bzoj 1798 区间乘一个数，区间加一个数，求区间和。注意乘和加的关系。
bzoj 1102 线段树水题，一个节点一个节点的建，保存上一次结果，以及序列长度即可
poj 2482 可以转化成多个矩形求交的覆盖次数最大。
hdu 4007 同上
hdu 4046 三个点看做一个点即可
hdu 2492 用树状数组比较简单，计算出前面比它大，比它小，后面比它大，比它小的数，再乘下，用long long。
poj 3225 区间扩大两倍表示点和线段，异或操作+覆盖操作
Codeforces Beta Round #43 D. Parking Lot 类似 poj3667 hotel 把路扩长 b + f ，这样的话，就不用考虑路端情况了，统一处理就好。。。 然后直接查找空位（len + b + f)，然后更新车长的那段(len)即可。
poj 2991 每个节点记录当前线段的初始坐标和终点坐标，还有这条线段和Y轴的夹角，注意中间更新左子树影响右子树，需要向量平移
hdu 3308 单点更新，查询区间最长连续上升序列长度。结点里建立三个域，从左边起最长的连续序列，从右边起，以及这个区间中最长的，注意查询合并
hdu 2781 几种类型结合+成端更新，细心即可
UESTC 1425 类似HDU 3308 小变形
hdu 3642 三维转化一维线段树，离散化z坐标，枚举z坐标，计算每层面积然后计算出体积
hdu 3255 类似上一个题，只不过把price当做z坐标，求长方体体积并
UVA 11983 覆盖K次矩形面积交，存当前区间覆盖0…k次的长度
hdu 3874 离线做，按结束坐标排序，然后扫一遍，遇到重复的，就把之前插入线段树的给删掉，删掉前面的不会影响后面的结果
OpenJudge POJ 1028 转化成矩形。按一维排序，然后动态插入，动态统计
hdu 4107 结点存当前区间伤害最小值，最大值，以及要加的伤害值。更新到如果最小值大于等于P，或者最大值小于P为止。