线段树—扫描线专题

hdu1542 Atlantis
矩形面积并
以前学线段树的时候对扫描线似懂非懂,关键是没明白为什么没有pushdown操作,现在总算弄懂了。。
因为在pushup里面当有线段覆盖时(cnt>0)直接对len域进行赋值,不依赖于儿子结点。这就相当于把这个结点当成了叶子结点(更新到底了),然后往上一路pushup,这样虽然导致该结点下面的结点信息可能有错,但是该结点以上的结点的信息保证正确。而询问是询问整段(len[1])的覆盖长度。这样每次询问时,根结点的信息是正确的就行了。

主席树

今天看了下主席树,感觉好神奇,代码精简而且实用,例如静态区间第k大之类的题,用主席树直接秒杀线段树套平衡树之类的写法。就是空间有点大。。
具体请参考:
1.clj的论文
2.博文一篇,代码写的很精炼:http://im.librazy.org/article/837/note-chairtree-via-functional-segtree/
其实很好理解的。
入门题:
hdu2665
静态区间第k小,注意题目描述可能不恰当。。

Time Limit : 4000/2000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 15   Accepted Submission(s) : 2

Font: Times New Roman | Verdana | Georgia

Font Size:

Problem Description

  给你一棵N个节点的树,其中1为根节点,每个节点有权值。一开始所有节点的权值均为0。现在我们要进行M次操作。
  一共有以下两种操作:
  1)1 u d 节点1到节点u的最短路径上的所有的节点(包括1,u)的权值增加d(1<=d<=300)
  2)2 u 查询节点u的权值

Input

  多组测试数据
  每组测试数据第一行有两个数N,M (1<=N,M<=60000)
  接下来N-1行 每行有两个数u,v (1<=u,v<=N且u!=v)表示节点u和节点v之间有一条边
  接下来M行,即M次操作,含义见题目描述

Output

  对于每个操作2,请输出u的权值

Sample Input

3 4
1 2
1 3
1 2 3
2 1
2 2
2 3

Sample Output

3
3
0

Source

test

昨天校赛,这题没想到思路,想到就很简单了。。这题很有意思
思路:如果给某个点加上一个值,从这个点到根的结点都要加上这个值,这样暴力肯定不行。以前做过把树求出dfs序,转化成线段树的题,但是那是对某棵子树的结点都加上一个值,那么这题如果dfs序的话,每次操作要加的那些结点在线段树中时不连续的,怎么解决呢
其实可以这样做,每次操作只修改该点的值,最后求点u的值,只要对以u为根的子树对应的区间求和就行了。。。
当然也可以用树状数组,我比较习惯线段树,虽然慢一些。。

hdoj1540 Tunnel Warfare

做了一些区间合并,现在已经比较理解了,关键一点是要知道,任何一个连续区,不断向下,一定会被分隔开。
这道题的query,要求包含节点x的1的连续长度。如果m+1-rmax[lson]<=pos && pos<=m+lmax[rson]那么直接返回这一段,否则x所在的连续1区间必定在左子区间或右子区间,继续往下找即可。

hdoj2871 Memory Control

这题前面部分和hotel那题是差不多的,也是寻找最左边连续的空白,成段更新,但是free时要输出free掉的起始点和结束点,get操作要输出第x个block的起始位置,这就比较烦了。开始用set,发现不行,因为要求kth并删除,我去,,难道要写splay。。这样代码也太长了吧。、果断谷歌之,发现是用vector解决的,vector可以在制定迭代器之前的位置插入元素,但是这样效率是o(n)吧。。。要是有5e4个查询是get x的话,岂不是效率超低?
解决两个问题:
(1)怎样知道unit x是属于哪个block的,可以维护一个域block[],当区间由多个内存块组成时block[id]=-1,block[id]=0表示id区间没有内存块覆盖。
(2)怎样get第x个(block是按起始点排序的)内存块的起始位置,按起始点维护一个vector。如上所述,插入和删除时先二分找到位置。
insert(iter,element);表示在迭代器iter的前面一个位置插入元素element。
这题比较考验耐心。。

hdoj3308 LCIS

单点修改的最长连续递增子序列
比前面几题都要简单,但是磨蹭了n久。。原因是query的时候没弄清楚,query的时候可能去左子区间也可能去右子区间,还有一种是答案是左右子区间拼起来的,想是想到了,但是还是写错了。。这种情况下应该是左起点选max(L,m+1-rmax[lson]),右起点选min(R,m+lmax[rson]).但是我原来写的时候只有当L<=m+1-rmax[lson] && m+lmax[rson]<=R的时候才考虑这种情况。。。

poj3667 Hotel

经典的区间合并的线段树
关于找满足要求长度的最左连续空闲区:
维护左起连续空闲区lmax,右起连续空闲区rmax,区间最长连续空闲区max。当区间max=len,若是则转入左子区间,否则看rmax[lson]+lmax[rson]是否>=len,若是,则直接返回m+1-rmax[lson],若还是不行,则忘右区间找一定能找到(因为已经确定max[id]>=len)。
为什么这样是正确的?
如果最终答案不是lmax那段,也不是rmax那段,而是当前区间中间的一段空白,那么如果它被两个子区间隔开,那么必然是rmax[lson]+lmax[rson],否则它必定在左子区间或右子区间,这种情况下会继续往下找。知道所求区间是lmax或rmax或rmax[lson]+lmax[rson]或到达叶子结点。所以只设置这些量是足够的。

poj2991 Crane——线段转化成向量,向量旋转

神奇的一道题,解法很奇妙————对我而言。。
题意:给出一些线段,起始时它们一次邻接的排列在二维笛卡尔坐标系上,端点分别是(0,w1)(0,w1+w2)……(0,w1+w1+……+wn),wi是第i个线段的长度。给出一些操作s,angle。表示把第s条线段的右端点p的后面的所有线段以p为中心旋转到p点两侧的线段成angle角度。(angle角度=以线段s以p点为中心逆时针转到与线段s+1重合经过的角度),要求每次操作后输出线段n右端点的坐标。
难点:直接做很麻烦,因为每次旋转的中心点可能不同,操作无法统一化表示,如果能统一化的话,就可以使用线段树了。
关键点:
1.把线段看成向量。
2.当进行操作是s,angle后,第s+1条线段开始的线段所在直线都旋转了angle角度。
3.向量(x1,y2)逆时针旋转a弧度后的端点坐标为
x1=x0*cos(a)-y0*sin(a);
y1=x0*sin(a)+y0*cos(a);
当顺时针旋转b弧度时,a=-b。相当与旋转了负角度。

有了这三个认识,题目就简单了。线段树中的结点(id,l,r)存储的是第l条线段的右端点到第r条线段的右端点表示的向量的右端点的横纵坐标。所以其实答案就是(x[1],y[1])。
那么怎样把题目告诉的旋转到成angle角度转化为旋转了多少角度呢?
这个简单,只要开个数组angle[],angle[i]表示第i条和第i+1条线段现在所成的角度。那么假如现在要旋转到成r弧度角,那么旋转了r-angle[i].注意化成弧度计算哦。

poj1436 Horizontally Visible Segments

终于ac了,不容易啊。。
题意:给出n条垂直的不相交线段,如果两条线段之间可以用一条不穿过其他线段的水平线段连接起来,那么称这两条线段互相可见。如果三条线段间两两可见,那么称这三条线段组成三角形,问总共有多少个三角形。
思路:每条线段的id(将线段按x坐标排序,id从1开始)作为颜色,用线段树维护区间的颜色。每次插入一条线段,就询问这段区间内有哪些颜色(也就是之前插入的哪些线段与当前线段互相可见),之后更新该区间的颜色。起始时整个区间颜色为0,当一段区间内有多种颜色时color设成-1。
注意一点:
| | |
| |
| | |
1 2 3
上图中x坐标=2的两条线段的y坐标分别为(1,2)(3,4),那么显然线段1和3是互相可见的,但是因为在线段树上插入线段3时[1,4]这个区间颜色全是2,所以会会认为线段3与1不是互相可见。这样就造成了漏数。
解决:方法是线段树的每个点乘2.这样x、x+1变成2x、2x+2,中间的2x+1这个点就可以表示区间(x,x+1).

poj3225 Help with Intervals——线段树

开始对于区间乘以2的方法没理解透彻导致错误。
由于涉及开闭区间,所以既要用到点又要用到区间。普通线段树实际上是将区间堪看成离散的点,每次操作都是对点进行操作,对连续的区间则无可奈何。
解决方法:对于数x,x乘2,2x表示点本身,2x+1表示(x,x+1)这段区间。这样问题就解决了。

zoj3686(ZOJ Monthly, March 2013 A题)

终于A了前不久比赛的A题,当时完全木有想到线段树啊,主要是对树的先序遍历序列的性质陌生:在树的先序遍历序列中,一棵子树占据连续的一段序列。所以求出先序序列的同时记录每个节点代表的子树的起始index和最后index。然后就能在o i的时候更新线段树[sub[i].begin,sub[i].end]部分即可。
被异或运算和成段更新坑了好久。。

poj2828——逆向思维的线段树

调试了好久,最后发现原来是顺着插入了。。
事后看了下被人的解题报告,主要是想看下怎样输出,自己用O(nlogn)时间输出,看了别人的代码,发现自己又二了,输出可以O(1)。。在update时找到插入位置后记录插入的叶子节点的l或r域即可,然后update()函数返回后写到结果数组的对应位置。暂时不改了,睡觉去也~