#516. 「LibreOJ β Round #2」DP 一般看规律

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: nzhtl1477

题目描述

给定一个长度为 nnn 的序列 aaa,一共有 mmm 个操作。
每次操作的内容为:给定 x,yx,yx,y,序列中所有 xxx 会变成 yyy

同时我们有一份代码:

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,mn,mn,m
第二行 nnn 个数,表示 a1,a2,⋯ ,ana_1,a_2,\cdots, a_na1,a2,,an
然后 mmm 行每行两个数 xxxyyy,表示序列中所有 xxx 会变成 yyy

输出格式

对于每次修改,输出答案。

样例

样例输入

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 1000001n,m100000

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