有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 }