1.hdu1166 敌兵布阵
查海生更新节点,区间求和
2.hdu1754 I Hate It
更新节点,区间最值
3.hdu1698 Just a Hook旱龟怎么养
手工制作大全简单
成段更新,总区间求和
4.hdu1394 Minimum Inversion Number
更新节点,区间求和(实现nlog(n)的逆序数方法,和树状数组比起来实在是有点鸡肋)
5.hdu1779 9-Problem C暂不公开
除号
成段更新,区间最值
6.pku2777 Count Color
成段更新,区间统计,位运算加速(我总把query里的传递给子节点的步骤忘了)
7.pku3468 A Simple Problem with Integers
成段更新,区间求和(中间乘法会超int..纠结了)
8.pku2528 Mayor’s posters
成段更新,区间统计(离散化)
9.hdu2795 Billboard
更新节点,询问特殊(暑假的时候不会线段树被这水题狂虐)
胡萝卜营养价值10.pku3667 Hotel
成段更新,寻找空间(经典类型,求一块满足条件的最左边的空间)
11.hdu1540 Tunnel Warfare
更新节点,询问节点所在区间(同上一道Hotel一样类型的题目)
睡眠不足会有哪些症状
12.hdu2871 Memory Control
hotel变形题目,三个都函数一样(vector忘记清空检查了好久)
13.hdu3016 Man Down
成段更新,单点查询(简单线段树+简单DP)
茶靡花14.hdu1542 Atlantis
矩形面积并,扫描线法(发现我们HDU的队员的矩形面积交模板基本都是在最坏情况下更新到底,宁波惨痛的教训啊..)
15.hdu1255 覆盖的面积
同上,扫描线法,我多加了一个系数csum,来统计覆盖两次的长度(156MS,第一次做线段树排到第一,纪念下)
16.hdu1828 Picture
扫描线,同面积统计,加了一个num_Seg统计一个扫描区域里的边
17.pku1436 Horizontally Visible Segments
成段更新,成段询问(染色问题,坐标*2后很简单,最后统计用暴力- -)
18.pku3225 Help with Intervals
成段更新,总询问区间(有个异或操作比较新颖)
19.pku2482 Stars in Your Window
成段更新,区间最值 + 扫描线(转化成区间最值有点巧妙,数据太TMD的恶心了,中间二分的地方会int溢出,检查了半个小时)
20.pku2828 Buy Tickets
思维很巧妙,倒过来做的话就能确定此人所在的位置
21.pku2464 Brownie Points II
更新节点,区间求和 + 扫描线(很好玩的一道题目,用两个线段树沿着扫描线更新,然后按”自己最多,对方最少”的方案一路统计)
(因为两棵树,我就直接写成类了)
22.pku3145 Harmony Forever
查找一个区间内最左边的数,询问的val大的话用线段树,小的话线性扫描,很囧的题目
工作祝福语23.pku2886 Who Gets the Most Candies?
寻找区间中的左数第N个数,约瑟夫环(学到了反素数表,可以不用把所有数字预处理出来了)
24.pku2991 Crane
记录了线段的两端点以及转过的角度,成段的转,超有意思的题目,做了之后会对线段树理解更深刻
(wy教主推荐的,不过我的代码写的太搓了..没啥学习的价值)
25.hdu1823 Luck and Love
二维线段树,没啥意思,代码量大了一倍而已,题目和运用范围都没一维的广,随便找了道题目练习下就好
