「SCOI2011」棘手的操作

发表于
字数统计: 1,319字 | 阅读时长 ≈ 6min

「SCOI2011」棘手的操作

题目描述

有 $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 输出所有节点中，权值最大的节点的权值。

输入格式

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

接下来一行输入 $N$ 个整数，$a_1,a_2,\ldots ,a_N$，代表 $N$ 个节点的初始权值。

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

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

输出格式

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

数据范围与提示

对于 $30\%$ 的数据，保证 $N\le 100,Q\le 10000$。

对于 $80\%$ 的数据，保证 $N\le 100000,Q\le 100000$。

对于 $100\%$ 的数据，保证 $N\le 300000,Q\le 300000$。

对于所有的数据，保证输入合法，并且 $-1000\le v,a_1,a_2,\ldots ,a_N\le 1000$。

看上去还是挺裸的可并堆，除了F3操作，只是要支持单点修改、区间修改、单点查询。

为了区间修改打标记，就不能用一个并查集处理连通问题，只能老老实实记录可并堆里面父亲节点是谁。查询时使用类似LCT中下放操作的方法，用一个栈依次下放从节点到根路径上每一个点即可。

事实上，本题单点修改比区间修改更恶心，因为区间修改不会改变堆的性质，而单点修改就必须把该点从堆里先删除出来，再修改，最后合并回去。如果采用的是左偏树，这个操作很可能会破坏左偏性质，而且由于下放操作的存在，并没有维护左偏性质的必要（效率上说不定更慢）。所以采用斜堆会比较容易。

对于F3操作，发现关注的只是所有堆顶元素的最值。为了快速得到所有堆顶元素的最大值，可以采用两种方式：
1.使用multiset，堆顶元素发生变化时做出相应的删除与添加操作即可。
2.开两个优先队列，采用“垃圾堆”的思路，将需要添加的元素放进一个堆，需要删除的元素放进另一个堆。如果两个堆顶元素相同，pop掉两个堆的堆顶元素即可。

下面的代码中采用的是方式2。

很久之前写的代码了，现在看起来很丑。

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
#include<stdio.h>
#include<queue>
#include<algorithm>
#define MAXN 600005
using namespace std;

int N,D;

priority_queue<int>Q,T;

int ls[MAXN],rs[MAXN],fa[MAXN],val[MAXN],lazy[MAXN];

void Putdown(int p)
{
	if(p==0||lazy[p]==0)return;
	if(ls[p])val[ls[p]]+=lazy[p],lazy[ls[p]]+=lazy[p];
	if(rs[p])val[rs[p]]+=lazy[p],lazy[rs[p]]+=lazy[p];
	lazy[p]=0;
}

int s[MAXN],Top;
int gf(int x)
{
	int i;
	s[++Top]=x;
	for(i=x;fa[i];i=fa[i])s[++Top]=fa[i];
	while(Top)Putdown(s[Top--]);
	return i;
}

int Merge(int x,int y)
{
	Putdown(x);Putdown(y);
	if(x==0||y==0)return x|y;
	if(val[x]<val[y])swap(x,y);
	rs[x]=Merge(rs[x],y);
	fa[rs[x]]=x;
	swap(ls[x],rs[x]);
	return x;
}

void U()
{
	int x,y;
	scanf("%d%d",&x,&y);
	x=gf(x);y=gf(y);
	if(x==y)return;
	T.push(val[x]);T.push(val[y]);
	Q.push(val[Merge(x,y)]);
}

int Del(int x)
{
	int f=fa[x],l=ls[x],r=rs[x],rt,y;
	rt=gf(x);
	y=Merge(l,r);
	ls[x]=rs[x]=fa[x]=0;
	if(ls[f]==x)ls[f]=y;
	else rs[f]=y;
	fa[y]=f;
	return gf(y);
}

void A1()
{
	int x,v;
	scanf("%d%d",&x,&v);
	int f=gf(x);
	T.push(val[f]);
	val[x]+=v;
	Q.push(val[Merge(x,Del(x))]);
}

void A2()
{
	int x,v;
	scanf("%d%d",&x,&v);
	x=gf(x);
	T.push(val[x]);
	val[x]+=v;lazy[x]+=v;
	Q.push(val[x]);
}

void F1()
{
	int x;
	scanf("%d",&x);
	gf(x);
	printf("%d\n",val[x]+D);
}

void F2()
{
	int x;
	scanf("%d",&x);x=gf(x);
	printf("%d\n",val[x]+D);
}

void F3()
{
	while(Q.size()&&T.size()&&Q.top()==T.top())Q.pop(),T.pop();
	printf("%d\n",Q.top()+D);
}

int main()
{
	int i,x,y,v,M;
	char op[5];

	scanf("%d",&N);
	for(i=1;i<=N;i++)scanf("%d",&val[i]),Q.push(val[i]);
	scanf("%d",&M);

	while(M--)
	{
		scanf("%s",op);
		if(op[0]=='U')U();
		else if(op[0]=='A')
		{
			if(op[1]=='1')A1();
			else if(op[1]=='2')A2();
			else scanf("%d",&v),D+=v;
		}
		else
		{
			if(op[1]=='1')F1();
			else if(op[1]=='2')F2();
			else F3();
		}
	}
}