Loj 2441 棘手的操作

Posted on | Views:

启发式合并.

对每个连通块,用一个 vector 维护块内所有点的编号,用一个可删堆维护块内所有权值,维护一个块加法标记 $tag$ .

用一个可删堆维护每个块的最大值中的最大值,维护一个全局加法标记 $Stag$ .

合并时直接用启发式合并,修改时先将对应的贡献在对应的可删堆中删掉,修改后再加回去.

时间复杂度 $O(n\log^2 n)$ ,但常数小,跑得还挺快的.

这样就可以搞到 Loj 上的代码最短了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=3e5+10;
int n,m,a[MAXN],bel[MAXN],tag[MAXN],Stag;
struct Heap
{
	priority_queue<int> q1,q2;
	void insert(int x)
	{
		q1.push(x);
	}
	int top()
	{
		while(!q2.empty() && q1.top()==q2.top())
			q1.pop(),q2.pop();
		return q1.top();
	}
	void erase(int x)
	{
		q2.push(x);
	}
}s[MAXN],S;
vector<int> id[MAXN];
void U()
{
	int x=read(),y=read();
	x=bel[x],y=bel[y];
	if(x==y)
		return;
	if(id[x].size()>id[y].size())
		swap(x,y);
	S.erase(s[x].top()+tag[x]);
	S.erase(s[y].top()+tag[y]);
	for(int i:id[x])
	{
		id[y].push_back(i);
		bel[i]=y;
		a[i]+=tag[x]-tag[y];
		s[y].insert(a[i]);
	}
	S.insert(s[y].top()+tag[y]);
}
void A1()
{
	int x=read(),v=read();
	S.erase(s[bel[x]].top()+tag[bel[x]]);
	s[bel[x]].erase(a[x]);
	a[x]+=v;
	s[bel[x]].insert(a[x]);
	S.insert(s[bel[x]].top()+tag[bel[x]]);
}
void A2()
{
	int x=read(),v=read();
	S.erase(s[bel[x]].top()+tag[bel[x]]);
	tag[bel[x]]+=v;
	S.insert(s[bel[x]].top()+tag[bel[x]]);
}
void A3()
{
	int v=read();
	Stag+=v;
}
int F1()
{
	int x=read();
	return a[x]+tag[bel[x]]+Stag;
}
int F2()
{
	int x=read();
	return s[bel[x]].top()+tag[bel[x]]+Stag;
}
int F3()
{
	return S.top()+Stag;
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
	{
		bel[i]=i;
		a[i]=read();
		id[i].push_back(i);
		s[i].insert(a[i]);
		S.insert(a[i]);
	}
	m=read();
	for(int i=1;i<=m;++i)
	{
		char buf[10];
		scanf("%s",buf);
		if(buf[0]=='U')
			U();
		else if(buf[0]=='A')
		{
			if(buf[1]=='1')
				A1();
			else if(buf[1]=='2')
				A2();
			else
				A3();
		}
		else
		{
			if(buf[1]=='1')
				printf("%d\n",F1());
			else if(buf[1]=='2')
				printf("%d\n",F2());
			else
				printf("%d\n",F3());
		}
	}
	return 0;
}