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为根的子树对应的区间求和就行了。。。
当然也可以用树状数组,我比较习惯线段树,虽然慢一些。。

zoj3765 Lights 平衡树

好吧,不得不承认,经过一个寒假的颓废啥都忘了。。
一道裸的splay,但是比赛的时候我一直觉得用splay维护gcd会不会出错。。。。因为我居然觉得旋转过程中gcd无法正确维护。。。。
思路:splay节点信息
on:节点是否是开灯状态
val0:该节点关灯时的值,如果该节点灯开着,那么val0=0,不影响结果。
val1:该节点开灯时的值,如果该节点灯关着,那么val1=0,不影响结果。
gcd0:以该节点为根的子树中所有状态为关的灯的gcd
gcd1:以该节点为根的子树中所有状态为开的灯的gcd
num[0]:以该节点为根的子树有多少个状态为关的灯
num[1]:以该节点为根的子树有多少个状态为开的灯
看来这个月要好好复习了。。。。

zoj 3761 Easy billiards dfs树

这题如果想到的话,写起来很简单。。
题意:无限大的二维坐标系中有n(0<=n<=2000)个球,可以用一个球沿与x坐标轴或y坐标轴平行的方向打球,如果球A碰到球B,那么球A停在球B的地方,球B以与A相同的方向前进,如果B运动的方向前方没有球了,那么判定球B出局,否则球B会撞到球C,以此类推,但是一个球不能直接出局,它必须是被某个球撞击后出局。
思路:把“相邻的球”(即可以直接撞击的球)连边,可以发现,同一个连通快中的球最后只会剩一个,,所以建图后dfs之,形成dfs树,为了保证一个连通块中的点撞到只剩一个,所以只要从子节点撞向父节点即可(比如,(0,0)、(1,0)、(0,1)三个点,dfs之后(0,0)是父节点,另两个是子节点,如果这时从(0,0)撞向(1,0)或(0,1)就会出错)
代码:

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)这段区间。这样问题就解决了。