[LOJ#516]「LibreOJ β Round #2」DP 一般看规律

试题描述

给定一个长度为 \(n\) 的序列 \(a\)，一共有 \(m\) 个操作。

每次操作的内容为：给定 \(x,y\)，序列中所有 \(x\) 会变成 \(y\)。

同时我们有一份代码：

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\) 个数，表示 \(a_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 \leq n, m \leq 100000\)

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

题解

启发式合并，维护每种数字在序列中的位置，用个 set 偷一发懒。【还有 unordered_map】

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

#include <unordered_map>

#include <set>

using namespace std;

int read() {

	int x = 0, f = 1; char c = getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }

	return x * f;

}

#define maxn 100010

unordered_map <int, int> id;

set <int> pos[maxn*3];

int n, q, cnt, real[maxn*3];

struct Que {

	int a, b;

	Que() {}

	Que(int _, int __): a(_), b(__) {}

} qs[maxn];

int main() {

	n = read(); q = read();

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

		int x = read();

		if(!id.count(x)) id[x] = ++cnt, real[cnt] = cnt;

		pos[id[x]].insert(i);

	}

	for(int i = 1; i <= q; i++) {

		int a = read(), b = read();

		qs[i] = Que(a, b);

		if(!id.count(a)) id[a] = ++cnt, real[cnt] = cnt;

		if(!id.count(b)) id[b] = ++cnt, real[cnt] = cnt;

	}

	int ans = 2147483647;

	for(int i = 1; i <= q; i++) {

		if(qs[i].a == qs[i].b){ printf("%d\n", ans); continue; }

		int a = id[qs[i].a], b = id[qs[i].b];

		if(pos[real[a]].size() > pos[real[b]].size()) swap(real[a], real[b]);

		a = real[a]; b = real[b];

		for(auto A: pos[a]) {

			set <int> :: iterator it = pos[b].lower_bound(A);

			if(it != pos[b].end()) ans = min(ans, *it - A);

			if(it != pos[b].begin()) ans = min(ans, A - *(--it));

			pos[b].insert(A);

		}

		pos[a].clear();

		printf("%d\n", ans);

	}

	return 0;

}

注：代码是 C++11 的，偷懒用 unordered_map 和 auto。

总有那么一段时间天天犯 SB。。。