洛谷P3273 [SCOI2011]棘手的操作

题目描述

有N个节点,标号从1到N,这N个节点一开始相互不连通。第i个节点的初始权值为a[i],接下来有如下一些操作:U x y: 加一条边,连接第x个节点和第y个节点A1 x v: 将第x个节点的权值增加vA2 x v: 将第x个节点所在的连通块的所有节点的权值都增加vA3 v: 将所有节点的权值都增加vF1 x: 输出第x个节点当前的权值F2 x: 输出第x个节点所在的连通块中,权值最大的节点的权值F3: 输出所有节点中,权值最大的节点的权值

输入输出格式

输入格式:

输入的第一行是一个整数N,代表节点个数。接下来一行输入N个整数,a[1], a[2], ..., a[N],代表N个节点的初始权值。再下一行输入一个整数Q,代表接下来的操作数。最后输入Q行,每行的格式如题目描述所示。

输出格式:

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

输入输出样例

输入样例#1

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

输出样例#1:

-10
10
10

说明

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

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

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

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

开两个可并堆堆

分别维护联通快最大值和所有的最大值

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

直接合并

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

先删掉,再加上原来的权值加v

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

跟线段树一样打个标记

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

直接用一个变量记录

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

直接输出

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

找到父亲,输出

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

输出维护最大值的那个堆的根节点

效率暂时rank1

  1 #include<cstdio>
  2 #include<cmath>
  3 #include<algorithm>
  4 #include<iostream>
  5 #include<queue>
  6 using namespace std;
  7 const int MAXN=300010;
  8 #define ls T[x].ch[0]
  9 #define rs T[x].ch[1]
 10 inline int read()
 11 {
 12     int a;
 13     cin>>a;
 14     return a;
 15 }
 16 int root,N,All;
 17 struct Priority
 18 {
 19     struct node
 20     {
 21         int fa,dis,val,ch[2],mark;
 22     }T[MAXN];
 23     void Clear(int x){ls=rs=0;T[x].fa=0;}
 24     void Pushdown(int x)
 25     {
 26         if(ls) T[ls].val+=T[x].mark,T[ls].mark+=T[x].mark;
 27         if(rs) T[rs].val+=T[x].mark,T[rs].mark+=T[x].mark;
 28         T[x].mark=0;
 29     }
 30     int Merge(int x,int y)
 31     {
 32         if(!x||!y)    return x+y;
 33         if( T[x].val < T[y].val)    swap(x,y);
 34         Pushdown(x);
 35         rs=Merge(rs,y);
 36         T[rs].fa=x;
 37         if(T[rs].dis>T[ls].dis) swap(ls,rs);
 38         T[x].dis=T[rs].dis+1;
 39         return x;
 40     }
 41     int Delet(int x)
 42     {
 43         Pushdown(x);
 44         int q=T[x].fa,p=Merge(ls,rs);
 45         T[p].fa=q;
 46         T[q].ch[ T[q].ch[1] == x] = p;
 47         while(q)
 48         {
 49             if(T[ T[q].ch[0] ].dis < T[ T[q].ch[1] ].dis)   swap( T[q].ch[0] , T[q].ch[1] );
 50             if(T[ T[q].ch[1] ].dis+1 == T[q].dis)   return root;
 51             T[q].dis=T[ T[q].ch[1] ].dis+1;
 52             p=q;q=T[q].fa;
 53         }
 54         return p;
 55     }
 56     int Find(int x)
 57     {
 58         while(T[x].fa) x=T[x].fa;
 59         return x;
 60     }
 61     int Sum(int x)
 62     {
 63         int ans=0;
 64         while(x=T[x].fa)  ans+=T[x].mark;
 65         return ans;
 66     }
 67     int AddPoint(int x,int v)
 68     {
 69         int fx=Find(x);
 70         if(fx==x)
 71         {
 72             if(ls+rs==0) 
 73                 {T[x].val+=v;return x;}
 74             else 
 75                 if(ls)  fx=ls;
 76                 else     fx=rs;
 77         }
 78         Delet(x);
 79         T[x].val+=v+Sum(x);
 80         Clear(x);
 81         return Merge(Find(fx),x);
 82     }
 83     int Build()
 84     {
 85         queue<int>q;
 86         for(int i=1;i<=N;i++)  
 87             q.push(i);
 88         while(q.size()>1)
 89         {
 90             int x=q.front();q.pop();
 91             int y=q.front();q.pop();
 92             int z=Merge(x,y);
 93             q.push(z);
 94         }
 95         return q.front();
 96     }
 97 };
 98 Priority h1,h2;
 99 int main()
100 { 
101     #ifdef WIN32
102     freopen("a.in","r",stdin);
103     freopen("b.out","w",stdout);
104     #else
105     #endif
106     char opt[20];
107     N=read();
108     h1.T[0].dis=h2.T[0].dis=-1;
109     for(int i=1;i<=N;i++)
110         h2.T[i].val=h1.T[i].val=read();
111     root=h2.Build();
112     int M=read();
113     while(M--)
114     {
115         scanf("%s",opt+1);
116         if(opt[1]=='U')
117         {
118             int x=read(),y=read();
119             int fx=h1.Find(x),fy=h1.Find(y);
120             if(fx!=fy)
121             {
122                    int tmp=h1.Merge(fx,fy);
123                 if(tmp==fx) root=h2.Delet(fy);
124                 else         root=h2.Delet(fx);//优化,根据大根堆的性质,以后的就没有用了    
125             }
126         }
127         else if(opt[1]=='A')
128         {
129             if(opt[2]=='1')
130             {
131                 int x=read(),v=read();
132                 root=h2.Delet(h1.Find(x));
133                 int y=h1.AddPoint(x,v);
134                 h2.T[y].val=h1.T[y].val;
135                 h2.Clear(y);
136                 root=h2.Merge(root,y);
137             }
138             else if(opt[2]=='2')
139             {
140                 int x=read(),v=read();
141                 int fx=h1.Find(x);
142                 root=h2.Delet(fx);
143                 h1.T[fx].val+=v;
144                 h1.T[fx].mark+=v;
145                 h2.T[fx].val=h1.T[fx].val;
146                 h2.Clear(fx);
147                 root=h2.Merge(root,fx);
148             }
149             else if(opt[2]=='3')
150             {
151                 int v=read();
152                 All+=v;
153             }
154             
155         }
156         else if(opt[1]=='F')
157         {
158             if(opt[2]=='1')
159             {
160                 int x=read();
161                 printf("%d\n",h1.T[x].val+h1.Sum(x)+All);
162             }
163             else if(opt[2]=='2')
164             {
165                 int x=read();
166                 printf("%d\n",h1.T[h1.Find(x)].val+All);
167             }
168             else if(opt[2]=='3')
169                 printf("%d\n",h2.T[root].val+All);
170         }
171     }
172 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏五分钟学算法

五分钟学会一个很有用的排序:归并排序

由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画...

1794
来自专栏小樱的经验随笔

洛谷 P1019 单词接龙【经典DFS,温习搜索】

P1019 单词接龙 题目描述 单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”...

3816
来自专栏数据结构与算法

BZOJ2212: [Poi2011]Tree Rotations(线段树合并)

可以证明,对于\(m\)个仅有一个元素,权值范围在\([1, n]\)的线段树合并的复杂度为\(mlogn\)

762
来自专栏北京马哥教育

python3急速入门 (二) 列表的使用

云豆贴心提醒,这是马哥Linux运维Python3急速入门系列第1篇文章 列表用于组织其它数值,即写在方括号之间、用逗号分隔开的数值列表。列表内的项目不必全是...

2965
来自专栏ACM算法日常

字符串的距离(动态规划) - leetcode 72

,因为在刷leetcode的动态规划专题。动态规划虽然定义很简单,但是对于复杂的动态规划题目,很多时候还是很棘手的。

852
来自专栏大闲人柴毛毛

剑指 offer——面试题8求旋转数组的最小值

题目:将一个非递减序列的某一处切一刀,再把前半段序列放到后半段序列的后面,这样组成的新序列叫做“旋转数组”。要求获取一个旋转数组的最小值。 这本质上是一个求最值...

3476
来自专栏微信公众号:Java团长

Java泛型详解

定义了一个List类型的集合,先向其中加入了两个字符串类型的值,随后加入一个Integer类型的值。这是完全允许的,因为此时list默认的类型为Object类型...

1032
来自专栏Petrichor的专栏

numpy: np.where

Note : 不接受 list 型的参数,只接受 `ndarray 型输入。

1203
来自专栏用户画像

7.6.2 内部排序算法的应用

1)若n较小(N<=50),则可以采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多,因而当记录本身信息量较大时,用简单选择排序...

701
来自专栏技术杂谈

给出一组非负整数,重新排序组成最大的数

先把对比的数字转成字符,拼接后再转成整数进行大小对比,即 int(a+b) 与 int(b+a) 进行降序排列。代码1。

6068

扫码关注云+社区

领取腾讯云代金券