2014
01-26

# Boring Game

Brian’s little sister Mary is fond of strange games involving lots of calculation. Unfortunately she’s not so good at mathematics so Brian’s often asked to calculate the values needed for her. Recently Brian’s facing another such problem:
An undirected graph with N vertexes and M edges is first drawn by Mary. Then, Mary randomly assigns an integer value to each of the vertexes. After that, Mary will perform a sequence of operations on the graph, each operation being of one of the following type:
a)  Among all vertexes connecting with vertex X via some edges, find the least value that is no less than value K. If such value cannot be found, zero will be returned instead.
b)  Updates the value assigned to vertex X to K.
c)  Erases an edge connecting vertex A and B from the graph.

There are multiple test cases in the input file. Each case starts with three integers, N, M, and Q (1 <= N <= 2 * 104, 0 <= M <= 6 * 104, 1 <= Q <= 3 * 105). The next N lines describe the initial value assigned to each vertex. The next part of each test case consists of M lines, and describes the edges in the graph at the beginning. Vertexes are numbered from 1 to N. The last part of each test case describes the operations to be performed on the tree. For operations of a) type, a line similar to “F X K” will be given; for operations of b) type, a line with the format of “U X K” will be given; and for c) type, the description will be given in the format similar to “E A B”. You can assume that there will always be at least one a) type query. The absolute value assigned to any vertex at any time will not exceed 10000.
There is a blank line between two successive cases. Input ends with End-of-File.

There are multiple test cases in the input file. Each case starts with three integers, N, M, and Q (1 <= N <= 2 * 104, 0 <= M <= 6 * 104, 1 <= Q <= 3 * 105). The next N lines describe the initial value assigned to each vertex. The next part of each test case consists of M lines, and describes the edges in the graph at the beginning. Vertexes are numbered from 1 to N. The last part of each test case describes the operations to be performed on the tree. For operations of a) type, a line similar to “F X K” will be given; for operations of b) type, a line with the format of “U X K” will be given; and for c) type, the description will be given in the format similar to “E A B”. You can assume that there will always be at least one a) type query. The absolute value assigned to any vertex at any time will not exceed 10000.
There is a blank line between two successive cases. Input ends with End-of-File.

3 3 8
4
5
8
1 2
2 3
1 3
F 1 4
E 1 3
F 2 7
E 2 3
E 1 2
F 2 7
U 3 6
F 3 3

1 0 1
0
F 1 0

Case 1: 4.500
Case 2: 0.000

Hint
For case 1, the answers for the queries are 4, 8, 0 and 6 respectively.


我们先不想其他的，考虑这个问题的三种操作要我们做什么。第一种操作就是找某个连通分量的大于k的最小点权，第二种和第三种如果是暴力q*n求解，那么就自然而然地模拟。

但是复杂度太高了，q为30万，n为2万，最多操作60亿次。因为有牵扯到连通分量，考虑用并查集做。那么第一个操作就是要找某个根所有儿子中权值大于k的最小值，着好像和我们平时做的并查集不一样，平时都是利用根的信息，这就是本题的一个亮点。第二个操作似乎要先找到根再来遍历儿子，再来更新点权，第三个操作似乎要将某个集合拆成两个集合。

这些操作如果正序来做，的确很吓人，第一个我们可以通过STL的set来应付，set的lower_bound方法不就是题目描述的这功能吗？第三个操作要拆集合很困难，但我们逆序转换成合并集合，则要简单、飘逸许多，也不影响结果。这就是本题的两个亮点。

分析差不多就这样，接着就是代码实现，我第一次用set操作，参看了百度和某神牛的代码，效率还不错，256ms，排名第三。

3 3 8
4 5 8
1 2
2 3
1 3
F 1 4
E 1 3
F 2 7
E 2 3
E 1 2
F 2 7
U 3 6
F 3 3
out: Case XX: 4.500

1 0 1
0
F 1 0
out: Case XX: 0.00

3 3 8
8 8 8
1 2
2 3
1 3
F 1 9
F 1 8
E 1 3
E 2 3
E 1 2
F 1 8
U 3 6
F 3 7
out: Case XX: 4.000

3 3 9
8 8 8
1 2
2 3
1 3
F 1 9
F 1 8
U 1 5
E 2 3
E 1 2
E 1 3
F 1 5
U 1 6
F 1 6
out:Case XX: 4.750

3 3 11
8 8 8
1 2
2 3
1 3
F 1 9
F 1 8
U 1 5
F 1 6
E 2 3
E 1 2
E 1 3
U 1 4
F 1 5
U 1 6
F 1 6
out: Case XX: 4.400

C艹代码：

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <set>
#include <algorithm>
using namespace std;
#define MAX 20010
#define PAIR pair<int,int>

struct Query {

char ope[3];
int  x,y;
}query[300010];
double ans;
int cost[MAX];						//cost[i]表示每个点的权值
int n,m,q,time,fa[MAX];				//fa[i]表示i属于哪个集合
multiset<int> map[MAX];				//存放图，本题将无向图转换为有向图，因为只要判是否连通
multiset<int> ver[MAX];				//存放以某点为父亲的所有节点

int GetPa(int x) {					//获取x点的父亲，并进行路径压缩

int p = x,tp;
while (p != fa[p]) p = fa[p];
while (x != p) {

tp = fa[x];
fa[x] = p,x = tp;
}
return p;
}
void UnionSet(int x,int y) {		//将y属于的集合和x属于的集合合并

int px = GetPa(x);
int py = GetPa(y);
if (px == py) return;
if (px > py) swap(px,py);

fa[px] = py;
multiset<int>::iterator it;
for (it = ver[px].begin(); it != ver[px].end(); ++it)
ver[py].insert(*it);		//合并时子节点也需要合并
}

int main()
{
int i,j,k,cas = 0,a,b,pa;

while (scanf("%d%d%d",&n,&m,&q) != EOF) {

for (i = 1; i <= n; ++i) {

fa[i] = i;
map[i].clear();
ver[i].clear();
scanf("%d",&cost[i]);
}
for (i = 1; i <= m; ++i) {

scanf("%d%d",&a,&b);	 //边从小点连到大点
if (a < b) map[a].insert(b);
else map[b].insert(a);
}

for (i = 1; i <= q; ++i) {  //先处理所有操作，再往回查询，加边

scanf("%s %d%d",query[i].ope,&a,&b);
query[i].x = a,query[i].y = b;
if (query[i].ope[0] == 'U') {
//保存原来的点权，并更新点权
query[i].y = cost[a];
cost[a] = b;
}
else if (query[i].ope[0] == 'E') {
//先删除这条边，后面再添加，这样不需要拆集合
if (a < b) map[a].erase(map[a].find(b));
else map[b].erase(map[b].find(a));
}
}

for (i = 1; i <= n; ++i)
ver[i].insert(cost[i]);
multiset<int>::iterator it;
for (i = 1; i <= n; ++i)	//用处理完的图建立并查集
for (it = map[i].begin(); it != map[i].end(); ++it)
UnionSet(i,*it);

ans = time = 0;
for (i = q; i >= 1; --i) {

a = query[i].x,b = query[i].y;
if (query[i].ope[0] == 'F') {

time++,pa = GetPa(a);
it = ver[pa].lower_bound(b);//set的这个方法很好地应付查询操作
if (it != ver[pa].end()) ans += *it;
}
else if (query[i].ope[0] == 'U') {
//更新回去
pa = GetPa(a);
it = ver[pa].find(cost[a]);
ver[pa].erase(it);
ver[pa].insert(b);
cost[a] = b;
}
else UnionSet(a,b);				//这一步是逆序处理的关键益处，变得异常简单
}

printf("Case %d: %.3lf\n",++cas,ans/time);
}
}