csdn364988181的博客

题目链接：http://poj.org/problem?id=3468题意：给出n个数，2种操作，一种将[l,r]中得数同时加上val，一种是查询[l,r]所有数之和思路：又是区间更新和查询(树状数组就可以很好的解决)，也是典型的线段树，lazy标志用法和之前有些不一样，每次更新成新区间的和与旧区间和的差值，查询时要把lazy标志向子节点推(这一步另外写一个函数会好看很多，

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1255题意：给出n个矩形求重叠的面积思路：将扫描线的有有效长度设置为要被覆盖2次以上的区域，覆盖2次的区域可以通过覆盖一次的区域求出来比较巧妙，详细看getlen函数就好，在做过普通扫描线的题目基础上很好理解#include #include #include

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1394题意：把第一个数放到最后一个，重复n-1次，问最小逆序数思路：先利用线段树求逆序数，将第一个数放到最后，n-a[i]（比a[i]大的数的个数）的逆序数会加1，再减去a[i]的逆序数（a[i]在最前面，逆序数为a[i]）#include #include #i

题目链接：http://poj.org/problem?id=2777题意：给出一面长度为len的墙，一开始的颜色是1，进行2种操作，一是将[l,r]涂成颜色p，二是询问[l,r]区间一共有多少种颜色思路：对区间进行修改和询问，很容易想到用线段树，但是如何保存有多少种颜色呢，因为颜色少于30种（我又看了题解），所以可以用位运算进行状态压缩，剩下的就是线段树普通的区间修改和更

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1828题意：求重叠矩形的周长思路：也是运用了扫描线，每一次更新后的tsum减去之前的tsum就是这次周长增长(上边处理理解有些不同，画了张图理解)，由于周长要计算所有的边要到cnt(面积只要到cnt-1#include #include #include #incl

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2795题意：有一个h*w的黑板，有n张1*w的海报，每张海报尽量往上帖(最上面是1)，同样高度则往左贴，输出每一张海报的高度，如果这张海报贴不上则输出-1思路：开始想到了用高度建树，保存每一个高度还剩下多少w，但是没想到怎么查询……，应该尽量往左字树进行查询，直到一个高度可以容纳

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2871题意：有内存大小为n，有4种操作：1.New x : 分配大小为x的内存，尽量靠左，输出左边界2.Free x : 释放包含x位置的内存块，输出左右边界3.Get  x : 返回第x个内存块的左边界，内存块要从左到右排序4 Reset : 恢复初始化的状态思

题目链接：http://poj.org/problem?id=3225&lang=zh-CN&change=true题意：对一个区间进行5种操作，问最后覆盖区间1.U T       当前区间上区间T2. I T       当前区间交上区间T3.D T      将当前区间和区间T的交去掉4.C T     将T区间中与当前区间的交去掉5.S T     DT并上

题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1542题意：给出一串匹配的括号，改变其中一个括号的方向，要求改变最左边的一个括号方向使得该串括号重新匹配思路：((()))这样一个串括号，我们每遇到‘(’便加1，遇到’)‘便建1这样可以得到序列：1 2 3 2 1 0，可以发现如果一串括号是匹配的，那么该序列的末尾

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1823题意：找出身高区间内满足和活泼值条件而且缘分值最高的女孩思路：二维线段树，也就是一维线段树的每一个节点再保存一颗线段树，一维线段树查询身高区间，然后再该保存该区间的节点构造一颗线段树，用活泼值维护保存最大的缘分值……整体建树不难，就是代码显得又长又丑，一维线段树查询区间，二

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1542题意：给出n个矩形的正对角线的2个端点，求面积并思路：线段树辅助扫描线求矩形面积并，第一次按照自己思路写这种题目，理解起来不算太困难，倒是写的时候各种奇葩错误。    首先对横坐标进行离散化，因为坐标是浮点数，方便建树以及减少时间消耗，用tsum保存有效长度，因此更新时

题目链接：http://poj.org/problem?id=2528题意：有N张海报，每张海报贴在[L,R]的区间上，问最后还能看见多少张海报思路：一开始在纠结如何保存一个区间有多少张海报，上一次填色的题目因为数据少，可以用二进制保存，这次数据非常大，不过因为只查询一次，直接遍历一次线段树就可以了，不过需要离散化，注意离散化的时候之间隔了1个数以上的2个数离散化时也要隔一

题目链接：http://poj.org/problem?id=3667题意：有n个连续的房间，有2种操作，一种是有若干个客人入住，要选择连续且尽量靠左的房间，输出最靠左的房间若没有则输出0，一种是将清空di后到di+x的房间清空思路：第一次做区间合并的题目主主要理解一下线段树的3个变量的用意义和更新方法lsum：从该区间左边界开始有多少个连续的房间，比如：0 0 0

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1166题意：给出一个n个数字，进行2种操作，更改一个数字大小或者询问一个区间所有数字的和思路：线段树典型的单点更新，区间询问，用树状数组也可以实现，s数组要从1开始，一时没注意查了好久#include #include #include #include #d

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1540题意：有n个相邻的村子，D操作将该村子与左右的连接切断，R操作是将上次切断的道路恢复，Q操作是询问包括x在内的连续的村子思路：线段树区间合并，和hotel不一样的是这题是单点更新，更新大同小异，因为是单点更新所以没用lazy标志，询问的时候比较不一样，判断改点是否在横跨左右

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1754题意：给出n个数字m次操作，操作分为2种，更新某一个数的大小和询问某一区间的最大值思路：很经典的线段树，单点更新以及查询区间，刚学习线段树按照别人的思路已经写过一次了，这次写的应该更贴近自己的想法#include #include #include #in

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3016题意：有n块木板，每一块木板有不同的高度h和左右端点的坐标xl和xr，从最高的木板下落，仅可以从木板的2个端点垂直下落，也就是当下落xi端点在下一块木板的[xl,xr]中才可以到达该木板，每一块木板有权值，初始值为100当初始值为0时死亡，问最好的情况到达地面(h=0)的时候权值最大

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1698题意：给出一段1~n的区间，区间内所有数初始为1，现在可以修改区间内任意一段，问m次修改后区间的和思路：区间更新以及区间询问，一个一个点进行修改复杂度太高，这里就使用了lazy标记，当整个区间都更改为val时，则用lazy标记该区间，并且更新sum，比较难理解的应该是只修改

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5316题意：给出一个大小为n的区间，2种操作，更新某一个点的值，或者查询[l,r]区间的“最大值序列”(要求该序列的下标奇偶相间)思路：线段树的单点更新和区间合并可以实现题目要求，我们维护4个数据就好，查询的比较特殊(1).区间里最大的以奇数开头和以奇数结尾的序列