[原创]516. 「LibreOJ β Round #2」DP 一般看规律 [set/SPLAY] 【STL/数据结构】

2017-07-04 21:01:07 Tabris_ 阅读数：274

博客爬取于2020-06-14 22:39:48
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/74356926

题目链接：https://loj.ac/problem/516
——————————————————————————————————————————
516. 「LibreOJ β Round #2」DP 一般看规律
内存限制：512 MiB
时间限制：1000 ms
标准输入输出
题目类型：传统
评测方式：文本比较
上传者： nzhtl1477
提交
提交记录
统计
测试数据
题目描述

给定一个长度为 n 的序列 a，一共有 m 个操作。
每次操作的内容为：给定 x,y，序列中所有 x 会变成 y。

同时我们有一份代码：

1
2
3
4
5
6
7
8
int ans = 2147483647;
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        if (a[i] == a[j])
            ans = std::min(ans, j - i);
    }
}
std::cout << ans << std::endl;

请在每次修改后输出代码运行的结果。
输入格式
第一行两个数，表示 n,m。
第二行 n 个数，表示a1,a2,⋯ ,ana_1,a_2,\cdots, a_n。
然后 m 行每行两个数 x 和 y，表示序列中所有 x 会变成 y。
输出格式
对于每次修改，输出答案。
样例
样例输入

5 10
2 7 6 3 8
6 1
7 1
1 3
5 6
1 7
9 5
1 10
7 6
7 5
3 9
样例输出

2147483647
1
1
1
1
1
1
1
1
1
数据范围与提示

1≤n,m≤1000001\le n , m \le 100000

每个出现的数字绝对值在 int 范围内。

——————————————————————————————————————————

首先能够明确,两个数的集合合并之后结果一定是越来越小的

所以就是怎么维护两个数的集合的问题了

最开始采用map<int,vector<int> >来维护

但是发现虽然最后维护的时候合并过程可以启发式优化
但是也需要将这个集合进行进行排序这样复杂度就爆炸了

然后想到用多颗SPLAY维护这个过程 ,然后码啊码,最后码炸了…

然后看了下由乃大佬的代码

发现居然可以用map<int,set<int> >进行维护

由于set本身就是一颗RB-tree了.所以不需要在手写平衡树了啊 .

事实证明STL非常强大啊 ,强大到爆啊.

附本题代码
——————————————————————————————————————————

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
int n,m,ans=2147483647;

map<int,set<int> >pos;

inline int read(){
    int x=0,f=1;char ch = getchar();
    for(;ch<'0'||'9'<ch;ch=getchar())if(ch=='-') f=-1;
    for(;'0'<=ch&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+ch-'0';
    return x*f;
}

inline void insert(int v,int x){
	set<int>::iterator it=pos[v].lower_bound(x);
	if(it!=pos[v].end()) ans=min(ans,*it-x);
	if(it!=pos[v].begin()) ans=min(ans,x-* --it);
	pos[v].insert(x);
}

int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++) insert(read(),i);
	while(m--){
		int x=read(),y=read();
		if(x!=y){
			if(pos[x].size()>pos[y].size()) swap(pos[x],pos[y]);
			for(set<int>::iterator it=pos[x].begin();it!=pos[x].end();++it) insert(y,*it);
			pos[x].clear();
		}
		printf("%d\n",ans);
	}
	return 0;
}