二次联通门 : LibreOJ #516. 「LibreOJ β Round #2」DP 一般看规律
/*
LibreOJ #516. 「LibreOJ β Round #2」DP 一般看规律 set启发式合并 题目中给定的代码意思求相同的数中间隔最小的值。 那么维护n个set就好
合并时把小的向大的上暴力合并 用了map所以不用离散化
*/
#include <iostream>
#include <cstdio>
#include <set>
#include <map> #define INF 2147483647 void read (int &now)
{
register char word = getchar ();
int temp = ;
for (; !isdigit (word); word = getchar ())
if (word == '-')
temp = ;
for (now = ; isdigit (word); now = now * + word - '', word = getchar ());
if (temp)
now = -now;
} std :: map <int, std :: set <int> > Need;
int N, M;
int Answer = INF; inline int min (int a, int b)
{
return a < b ? a : b;
} inline void Insert (int pos, int x)
{
std :: set <int> :: iterator now = Need[pos].lower_bound (x);
if (now != Need[pos].end ())
Answer = min (Answer, *now - x);
if (now != Need[pos].begin ())
Answer = min (Answer, x - *-- now);
Need[pos].insert (x);
} int main (int argc, char *argv[])
{
read (N), read (M);
int x, y;
for (int i = ; i <= N; i ++)
{
read (x);
Insert (x, i);
} for (; M; -- M)
{
read (x), read (y); if (x != y)
{
if (Need[x].size () > Need[y].size ())
std :: swap (Need[x], Need[y]);
for (std :: set <int> :: iterator i = Need[x].begin (); i != Need[x].end (); ++ i)
Insert (y, *i);
Need[x].clear ();
}
printf ("%d\n", Answer);
} return ;
}