题意：
给出N（<=1e5）个操作，操作分为两种，①在集合中添加一个数x，②问这个集合中mod x 的最小值是多少。（x <= 3e5）
题解：
0.首先我们发现log家族中有算法满足这道题目，那么采用分块的思想。
1.那么对于小于根号下MAX(x)的询问，直接暴力维护答案，对于大于根号MAX(x)的询问，只需要找到第一个大于等于K * x 的值是多少。
2.那么现在问题是维护第一个大于等于K * x 的值是多少，现在有两种选择，①用STL中的<set> 中的 lower_bound 复杂度为logx ②用并查集充当链表 复杂度很小
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int block = 507;
const int N = 3e5 + 7;
char ch[2];
int pa[N], x, q[N], o[N], ans[N], mini[N], n, cnt;
int find (int x) {
return pa[x] == x ? x : pa[x] = find (pa[x]);
}
int main () {
scanf ("%d", &n);
memset (mini, 127, sizeof mini);
for (int i = 0; i < N; ++i) pa[i] = i + 1;
for (int i = 1; i <= n; ++i) {
scanf ("%s%d", ch, &x);
if (ch[0] == ‘A‘) {
o[i] = 1;
q[i] = x;
pa[x] = x;
for (int i = 1; i <= block; ++i) {
mini[i] = min (mini[i], x % i);
}
}
else if (ch[0] == ‘B‘) {
o[i] = 2;
q[i] = x;
if (q[i] <= block) ans[i] = mini[q[i]];
}
}
for(int i = N - 1;i >= 0; --i) pa[i] = find(pa[i]);
for (int i = n; i >= 1; --i) {
if (o[i] == 1) pa[find (q[i])] = pa[find (q[i] + 1)];
else if (o[i] == 2) {
if (q[i] > block) {
int ret = 1e9+7;
for (int j = 0; j < N; j += q[i]) {
if (find (j) == N) continue;
ret = min (ret, find(j) % q[i]);
}
ans[i] = ret;
if (ret == 1e9+7) ans[i] = q[i] - 1;
}
}
}
for (int i = 1; i <= n; ++i) if (o[i] == 2) printf ("%d\n", ans[i]);
return 0;
}
总结：
合理运用并查集当链表的性质QAQ
BZOJ 4320 ShangHai2006 Homework
原文：http://www.cnblogs.com/xgtao/p/5967984.html