HPOJ1015题解

发表于 | 评论数： | 阅读次数：

第一道自己出的数据结构，并且一发过了大样例的题目。

以及自创的第二个玄学数据结构。

题目描述

指定一种数据结构，要求支持以下操作：
1.向这个数据结构内加入一个新元素，并为其指定一个所属集合
2.合并分属于集合$i$和集合$j$的元素。
3.输出某一个集合$i$内权值最大的数

注：程序开始时，该数据结构为空

输入输出格式

输入格式

第一行，一个正整数$n$，表示有$n$个操作。
第$2$到$n+1$行，每行有两个或三个元素：

  • 1 x y表示将新元素$x$加入到编号为$y$的集合中
  • 2 i j表示合并编号分别为$i$和$j$的集合，表示把$j$集合以内的元素合并到$i$集合中
  • 3 i表示输出编号为$i$的集合内权值最大的元素，如果不存在指定集合，输出-1。

输出格式

每一个操作3的答案。

INPUT & OUTPUT‘s example s

Input’s eg #1

1
2
3
4
5
6
7
8
9
10
11
10
1 1 2
1 4 2
1 6 1
1 7 3
3 2
1 8 3
2 1 2
1 4 6
3 1
1 4 7

Output’s eg #1

1
2
4
6

说明

对于$50 \%$的数据，$1 \leq n \leq 10^3$
对于$100 \%$的数据，$1 \leq n \leq 2 \times 10^5$

分析

本题就是一道Payphone-XSet的板子题，至于这种玄学数据结构到底是怎么样的，嗯嗯，我还是讲讲吧。

首先，Payphone-XSet可以支持的操作有：

  • 将一个值插入一个集合中，如果当前没有此集合，那么就新建一个集合。
  • 求一个集合的元素数量，最大值，最小值，和。。。
  • 合并两个集合。
  • 销毁一个集合。
  • 返回一个元素属于哪一个集合

时间复杂度均为$O(1)$,空间复杂度为$O(n)$。

似乎，有点像并查集，但显然没有并查集强大。

不多说了，直接上代码，绝对简单易懂，玄学到死。

代码

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
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<climits>
#include<algorithm>
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*its=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==its)
            its=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==its)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
} 
using namespace FastIO;
/* definitions */
const int MAXN = 1e4+9;
const int MAX_DATA = -0x7fffffff;
int n;
struct Node{
	int cnt;
	int max=MAX_DATA;
};
Node k[MAXN];

/* functions */
inline int Hash(int x){
	return x%MAXN; 
}
inline void pushIn(int x,int y){
	k[Hash(y)].cnt++;
	k[Hash(y)].max=std::max(k[Hash(y)].max,x);
} 
inline void Merge(int x,int y){
	if(x==y)return;
	k[Hash(x)].cnt+=k[Hash(y)].cnt;
	k[Hash(y)].cnt=0;
	k[Hash(x)].max=std::max(k[Hash(x)].max,k[Hash(y)].max);
	k[Hash(y)].max=MAX_DATA;
}
inline int QueryMax(int y){
	if(k[Hash(y)].cnt==0)return -1;
	return k[Hash(y)].max;
}
int main(int argc,char *argv[])0{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int op;
		scanf("%d",&op);
		if(op==1){
			int x,y;
			scanf("%d%d",&x,&y);
			pushIn(x,y);
		} 
		if(op==2){
			int x,y;
			scanf("%d%d",&x,&y);
			Merge(x,y);
		}
		if(op==3){
			int k;
			scanf("%d",&k);
			int ans=QueryMax(k);
			printf("%d\n",ans);
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
} 
//k[i].cnt --> card{set(i)}
//k[i].max --> max{set(i)}

THE END