【bzoj2333】 [SCOI2011]棘手的操作

2014年12月23日4,7089

Description

有N个节点,标号从1到N,这N个节点一开始相互不连通。第i个节点的初始权值为a[i],接下来有如下一些操作:

U x y: 加一条边,连接第x个节点和第y个节点

A1 x v: 将第x个节点的权值增加v

A2 x v: 将第x个节点所在的连通块的所有节点的权值都增加v

A3 v: 将所有节点的权值都增加v

F1 x: 输出第x个节点当前的权值

F2 x: 输出第x个节点所在的连通块中,权值最大的节点的权值

F3: 输出所有节点中,权值最大的节点的权值

Input

输入的第一行是一个整数N,代表节点个数。

接下来一行输入N个整数,a[1], a[2], …, a[N],代表N个节点的初始权值。

再下一行输入一个整数Q,代表接下来的操作数。

最后输入Q行,每行的格式如题目描述所示。

Output

对于操作F1, F2, F3,输出对应的结果,每个结果占一行。

Sample Input

3
0 0 0
8
A1 3 -20
A1 2 20
U 1 3
A2 1 10
F1 3
F2 3
A3 -10
F3

Sample Output

-10
10
10

HINT

对于30%的数据,保证 N<=100,Q<=10000

对于80%的数据,保证 N<=100000,Q<=100000

对于100%的数据,保证 N<=300000,Q<=300000

对于所有的数据,保证输入合法,并且 -1000<=v, a[1], a[2], …, a[N]<=1000

题解

离线+线段树。。。??

不我怎么弱当然只会直接模拟。。。

给连通块增加一个值以及合并连通块,维护最大值

我们需要一个手写的可并堆,斜堆极好。。。

然后还要维护全局最大值,支持修改结点。。。

唔再来个可并堆也行,因为我比较偷懒,所以用了个set

其实用pb_ds的配对堆似乎更优越

U 找到x,y所在堆的堆顶,较小的从set中删除,合并两个堆

A1 处理x祖先的标记,把x所在堆顶删出set,把x从堆中取出,加完v再放进去,堆顶放入set

A2 x所在堆顶删出set,堆顶打标记,改权值后放回set

A3 开个变量存起来TAT

F1 处理x祖先的标记,输出

F2 输出x所在堆顶

F3 输出set中最大值

嘴巴上AC果然简单。。。

嫌我写的太sb的话大家还是看pyc神犇的blog吧

http://blog.csdn.net/charlie_pyc/article/details/20830305

我会告诉你我对拍半天的错误数据是。。。?如下

input

2
0 0
3
U 1 2
A1 1 -8
F3

output

0

。。。我负数乱做。。。跪烂了

顺便附sb的数据生成器

数据生成器

代码。。。

 

  • LYK2015年4月30日 下午1:17 回复

    实测61行是没有必要的(然而时间并没有快多少)

    #1  
  • czk2016年2月24日 下午2:14 回复

    左偏树这样一直网上找根复杂度不会爆炸吗?

    #2  
    • hzwer2016年3月6日 上午12:42 回复
      admin

      左偏树可以认为一直保持着不错的平衡,那么深度就是logn的

      #21
      • orzhzwer2016年5月31日 下午10:11 回复

        然而实力被卡

        #22
      • mektpoy2016年8月31日 下午7:02 回复

        左偏树和斜堆的深度都是最坏O(n)的

        #22
        • 蒟蒻2016年9月10日 下午9:36 回复

          实际最好是ON的

          #23
  • wjyi2016年5月31日 下午5:56 回复

    这个左偏树为什么不记录深度啊,代码里直接交换了左右子树

    #3  
    • AliceWang2016年5月31日 下午6:48 回复

      这个并不是左偏树,而是斜堆

      #31
      • wjyi2016年5月31日 下午8:34 回复

        (⊙v⊙)嗯,谢谢

        #32