给定一个长度为 n 的序列 a，一共有 m 次操作，
每次操作给定 x, y，使序列中所有 x 变成 y，问每次操作后，值相等的位置的最小下标差是多少。若序列中无相同的数，则输出2147483647。

n, m <= 1e5, 所有数在int范围内

题目链接

对于这道题，ans明显是只减不增的。而且对ans造成的影响必然是x变成y后使得y的距离变小了。试图从这里着手。

我们需要一种数据结构来将x, y合并，并求出下标的最小差。很显然不可能int范围内所有值都开一个这种数据结构，必定会空间爆炸。由于此题数值的大小和具体值不对答案产生影响，所以可以直接离散化，然后进行操作。我比较懒，就直接用set来水。每次操作后暴力判断最小的下标差

然后我就T了。

WA T 的一声哭了出来

发现读入数据很多，输出数据也很多，所以加一个快读快输试试。

然后只快了300ms，又T了。

之前说了，ans是只减不增的，所以当ans为1的时候后面的答案一定都为1了，不用进行合并，暴力判断这种很费时间的操作了。并且这道题其实答案很容易变成1，我也不知道为什么。

然后就A过去了。跑的比我想象的快多了

还顺便上了统计第一页，好开心

#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>

//懒的加fread，否则可能更快
void input(int &var) {
  int ope = 1;
  var = 0;
  char ch = getchar();
  while((ch < '0' || '9' < ch) && ch != '-') ch = getchar();
  if(ch == '-') {
    ope = -1;
    ch = getchar();
  }
  while('0' <= ch && ch <= '9') {
    var = var * 10 + ch - '0';
    ch = getchar();
  }
  var *= ope;
  return;
}

//懒的加fwrite
void output(int num) {
  if(num < 0) {
    putchar('-');
    num = -num;
  } else if(num == 0) {
    putchar('0');
    return;
  }
  if(num > 9) {
    output(num / 10);
  }
  putchar(num % 10 + '0');
  return;
}

const int MAX_LEN = 100000;
const int MAX_ASK_NUM = 100000;

struct Query {
  int before;
  int after;
} query[MAX_ASK_NUM];

int num;
int askn;

int arr[MAX_LEN + 1];
std::vector<int> vec;

std::set<int> tree[MAX_LEN + (MAX_ASK_NUM << 1) + 5];

void init();
void solve();

int main() {
  init();
  solve();
  return 0;
}

int getId(int key) {
  return std::lower_bound(vec.begin(), vec.end(), key) - vec.begin();
}

void init() {
  input(num);
  input(askn);
//  scanf("%d%d", &num, &askn);
  for(int i = 1; i <= num; ++i) {
    input(arr[i]);
//    scanf("%d", arr + i);
    vec.push_back(arr[i]);
  }

  for(int i = 1; i <= askn; ++i) {
    input(query[i].before);
    input(query[i].after);
//    scanf("%d%d", &query[i].before, &query[i].after);
    vec.push_back(query[i].before);
    vec.push_back(query[i].after);
  }

  sort(vec.begin(), vec.end());
  vec.erase(std::unique(vec.begin(), vec.end()), vec.end());

  for(int i = 1; i <= num; ++i) {
    arr[i] = getId(arr[i]);
    tree[arr[i]].insert(i);
  }

  for(int i = 1; i <= askn; ++i) {
    query[i].before = getId(query[i].before);
    query[i].after = getId(query[i].after);
  }

  return;
}

void solve() {
  int ans = 0x7fffffff;
  int loc = askn + 1;
  for(int i = 1; i <= askn; ++i) {
    tree[query[i].after].insert(tree[query[i].before].begin(), tree[query[i].before].end());
    tree[query[i].before].clear();

    std::set<int>::iterator i1 = tree[query[i].after].begin(), i2 = tree[query[i].after].begin();
    if(i2 != tree[query[i].after].end()) {
      ++i2;
      while(i2 != tree[query[i].after].end()) {
        ans = std::min(ans, *i2 - *i1);
        ++i1;
        ++i2;
      }
    }
    if(ans == 1) {
      loc = i;
      break;
    }
    output(ans);
    putchar('\n');
//    printf("%d\n", ans);
  }
  while(loc++ <= askn) {
    putchar('1');
    putchar('\n');
  }
  return;
}