题解 P5397【[Ynoi2018] 天降之物】/ 第四分块
题目描述
一个长为 \(n\) 的序列 \(a\)。
你需要实现 \(m\) 个操作，操作有两种：
- 把序列中所有值为 \(x\) 的数的值变成 \(y\)。
- 找出一个位置 \(i\) 满足 \(a_i=x\)，找出一个位置 \(j\) 满足 \(a_j=y\)，使得 \(|i-j|\) 最小，并输出 \(|i-j|\)。
本题强制在线。
对于 \(100\%\) 的数据，所有数在 \([1,10^5]\) 内，每次操作的值不超过 \(n\)。
第一个操作的处理方法
第一个操作比较有启发性，考虑单独拿出来看一下会不会做。就当询问是单点查询，或者没有询问，能维护就行。
第一种做法
我们暴力维护 \(a_i\)。但是会被出现次数太多的颜色集体换另一种没有出现的颜色卡掉。所以改变 \(a_i\) 含义。记录真实值 \(a_i=v\) 在程序中被记为 \(b_i=mp_v\)。初始，出现过的 \(v\) 有 \(mp_v=v\)，没有出现过的有 \(mp_v=\varnothing\)。这样以后，每次做合并两种颜色的操作，例如将所有 \(x\) 改为 \(y\)，如果 \(x\) 的出现次数（在程序中记为 \(siz[mp_x]\)）大于 \(y\) 的出现次数，考虑交换 \(mp_x\) 与 \(mp_y\)（注意 \(x, y\) 不动）的值，这样的意思是原地交换 \(x, y\) 在真正的 \(a_i\) 中的出现，原来真正的 \(a_i=x\)（\(b_i=mp_x\)）换成 \(a_i=y\)（\(b_i=mp_y\)，此时 \(b_i\) 的值没有变过，但问起 \(b_i\) 的值时就发现它代表 \(a_i=y\)），反之也一样。这样以后再做“将所有 \(x\) 改为 \(y\)”的操作，与原来想要的结果一致。那我们就可以暴力做启发式合并了：记录 \(P[mp_v]\) 表示 \(v\) 的所有出现位置，然后将两个 \(P\) 集合合并，并暴力更新 \(b_i\)。
第二种想法
这个想法基于一个并查集。我们维护并查集 \(parent[i]\) 表示 \(a_i\) 和哪些下标的数字是相等的（注意说的是下标），等会将它们合并。\(parent[i]\) 具有树形结构，在根上，即 \(parent[i]=i\) 的 \(i\) 上，维护 \(value[i]\) 表示 \(a_i\) 的真实值是多少。这样以后查询 \(a_i\) 就是查询 \(value[find(i)]\)，其中 \(find(i)\) 是并查集找根的操作。另外记一个 \(repr[v]\)（是 representation 的缩写），满足若 \(parent[i]=i\land value[i]=v\) 则 \(repr[v]=i\)，否则不存在时 \(repr[v]=\varnothing\)。
考虑初始化怎么做，如果给你一个 \(a_i\) 怎么维护这些东西？为了正确维护 \(repr[v]\)，我们按照随机顺序访问 \(a_i\)，考虑：
- 若 \(repr[a_i]=\varnothing\)，则使得 \(parent[i]=repr[a_i]=i, value[i]=a_i\)。
- 否则 \(parent[i]=repr[a_i]\)。
这样的正确性显然。
考虑操作怎么做，将所有 \(x\) 改为 \(y\) 时，考虑记 \(repr[x]=i\) 以后：
- 若 \(repr[y]=\varnothing\)，则进行移花接木，使得 \(repr[y]=i, value[i]=y\) 以后 \(repr[x]=\varnothing\)。
- 否则在并查集上合并，\(parent[i]=repr[y]\) 即可。然后还要 \(repr[x]=\varnothing\)。
单点查询直接输出 \(a_i=value[find(i)]\)。
第二种想法的复杂度
假如是进行 \(m\) 次操作输出整个 \(a_i\) 序列，复杂度其实是 \(O(n+m)\)。考虑 \(m\) 次操作全部是 \(O(1)\)。最终 \(find(i)\) 做 \(n\) 次，你发现这个并查集如果路径压缩，则每个点只会被有效向上递归一次，然后就被压缩了，这样就是线性了。这和先 merge 再 query 的并查集是差不多的，后者也是严格的线性。但是 merge 与 query 交错的并查集就不能这么分析，要写完路径压缩和启发式合并也只能做到 \(O(n\alpha(n))\)。
总结
这样以后再参考一下 这篇神仙题解 就会了第一分块。然后发现两种想法其实差不多？核心都是那个 \(mp_v\) 或者 \(repr[v]\) 数组，前者用启发式合并完成合并，后者用并查集。
solution：根号分治
设置阈（读作 yu4）值 \(B\)，为了方便思考先假定 \(B=\sqrt n\)。将出现次数 \(\leq B\) 的颜色 \(c\) 成为小团，\(>B\) 的颜色 \(c\) 成为大团。然后发现只会有 \(O(n/B)\) 个大团。
- 小团与小团之间的查询，若已经维护各自有序的出现位置集合，则可以以 \(O(B)\) 的归并排序完成。
- 大团与大团之间的查询，只会有 \(O(n^2/B^2)\) 种可能的询问，暴力预处理之。具体来说，已知一个大团和整个 \(a_i\) 当前的样子，直接扫描整个序列就可以处理出对其它团的答案，\(O(n)\) 可以计算之。
- 小团与大团之间的查询，有一种想法是维护有序的大团的出现位置集合，然后二分查找。但是这一部分复杂度是 \(O(B\log n)\)，令人不满，有可能最终复杂度会爆出 \(O(n\sqrt n)\)。等会需要另辟蹊径，但我们先看看其他的。
- 小团与小团合并，直接 \(O(B)\) 的归并排序；若合并以后成为大团，这样的事情最多发生 \(O(n/B)\) 次，以 2. 中方法预处理答案。
- 大团与大团合并，只会发生 \(O(n/B)\) 次，同样以 2. 中方法预处理答案。
- 小团向大团合并，一种基于二分查找的方法就是你用
std::set维护出现位置集合，然后暴力插入（只会插入 \(O(n)\) 次）。然后暴力求解一遍这个小团与其他大团的答案，更新进入预处理的答案。若以 2. 的方法做，则这一部分总的复杂度达到 \(O((n^2/B)\log n)\)。非常草率。 - 大团向小团合并，以 \(O(1)\) 代价交换一些
std::set和各种编号，然后更新其他大团的预处理答案 \(O(n/B)\)，以将大团与小团原地交换。然后应用 6. 中方法。 - 所以你的复杂度是 \(O((n^2/B)\log n)\) 与 \(O(mB\log n)\) 取最大值，令人忍俊不禁。
另辟蹊径，优化小团与大团的操作部分，避开直接做它们之间的合并与查询。将颜色 \(c\) 的出现位置集合拆为主要集合 \(S[c]\) 与附加集合 \(P[c]\)，其中 \(|P[c]|\leq B\)，而 \(|S[c]|\) 可能非常巨大。规定小团的 \(S[c]=\varnothing\)。
-
在大团预处理答案时，改为预处理用当前的 \(S[c]\cup P[c]\)（意思是以后 \(P[c]\) 会变）去预处理向所有团的答案。
-
小团 \(x\) 与大团 \(y\) 之间的查询，拆为之前预处理的答案（\(S[y]\) 向 \(x\)）与剩下的附加的暴力 \(P[y]\) 向 \(x\)）两部分。
-
小团 \(x\) 向大团 \(y\) 合并，改成暴力合并两个 \(P\) 集合，然后可以用之前算过的另一个大团 \(c\) 向 \(P[x]\) 的答案合并到 \(c\) 向 \(y\) 的答案。
-
大团向小团合并，感觉这里可以维护 \(S[c]\) 然后交换两种颜色的信息（记得在预处理答案部分将 \(a_i\) 数组正确重构，重要）。或者可以应用上面“第一个操作的第一种做法“记录一个 \(mp_v\) 表示真实值，只做一次 swap，和之前说的部分完全匹配。
总之这样就能够修正了。具体细节参见代码算了。
solution：序列分块
序列分块。维护每一块的，每种颜色的最左出现和最右出现，还有每一块的两种颜色之间的答案。查询直接将所有最左 / 右出现拉出来跑归并排序，以及每一块的答案。修改时直接最左 / 右出现合并交换感觉就行了，因为每一块都是独立的，而且每种颜色信息比较少。就用 \(mp_v\) 之类的直接改。口胡的，没有代码。
code（根号分治）
\(O(n\sqrt n\log n)\) 令人忍俊不禁
constexpr int B = 300;
int n, m, a[200010];
set<int> pos[200010], bigs;
vector<int> bans[200010];
int solvebf(int x, int y) {
if (pos[x].size() > pos[y].size()) swap(x, y);
int ans = 1e9;
for (int p : pos[x]) {
auto it = pos[y].lower_bound(p);
if (it != pos[y].end()) ans = min(ans, *it - p);
if (it != pos[y].begin()) ans = min(ans, p - *prev(it));
}
return ans;
}
vector<int> generateb(int b) {
vector<int> ans(1e5 + 1, 1e9);
for (int c = 0; c <= 1e5; c++) for (int p : pos[c]) a[p] = c;
int lst = 0;
for (int p : pos[b]) {
for (int j = lst + 1; j < p; j++) {
ans[a[j]] = min(ans[a[j]], p - j);
if (lst) ans[a[j]] = min(ans[a[j]], j - lst);
}
lst = p;
}
for (int j = lst + 1; j <= n; j++) ans[a[j]] = min(ans[a[j]], j - lst);
return ans;
}
int main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i], pos[a[i]].insert(i);
for (int c = 0; c <= 1e5; c++) if (pos[c].size() > B) bigs.insert(c), bans[c] = generateb(c);
for (int t = 1; t <= m; t++) {
static int lstans = 0;
int op, x, y;
cin >> op >> x >> y;
x ^= lstans, y ^= lstans;
if (op == 1) {
if (x == y) continue;
if (max(pos[x].size(), pos[y].size()) <= B) {
if (pos[x].size() > pos[y].size()) swap(pos[x], pos[y]);
// if (!pos[x].empty()) pos[y].insert(pos[x].begin(), pos[x].end());
for (int p : pos[x]) pos[y].insert(p);
// 就直接 pos[y].insert(pos[x].begin(), pos[x].end()) 就行了，考试机器不知道为啥这里 RE
pos[x].clear();
if (pos[y].size() > B) {
bigs.insert(y), bans[y] = generateb(y);
for (int b : bigs) if (b != y) bans[b][y] = bans[y][b];
}
} else if (min(pos[x].size(), pos[y].size()) > B) {
for (int b : bigs) if (b != x && b != y) bans[b][y] = min(bans[b][y], bans[b][x]);
// if (!pos[x].empty()) pos[y].insert(pos[x].begin(), pos[x].end());
for (int p : pos[x]) pos[y].insert(p);
pos[x].clear();
bans[y] = generateb(y);
bigs.erase(x);
} else {
if (pos[x].size() > pos[y].size()) {
// 两种颜色原地交换
assert(bigs.find(x) != bigs.end());
assert(bigs.find(y) == bigs.end());
bigs.erase(x);
for (int b : bigs) bans[b][y] = bans[b][x]; // cover
bigs.insert(y);
swap(bans[x], bans[y]);
swap(pos[x], pos[y]);
}
for (int b : bigs) if (b != y) {
int ret = solvebf(b, x);
bans[b][y] = min(bans[b][y], ret);
bans[y][b] = min(bans[y][b], ret);
}
// if (!pos[x].empty()) pos[y].insert(pos[x].begin(), pos[x].end());
for (int p : pos[x]) pos[y].insert(p);
pos[x].clear();
}
} else {
if (pos[x].empty() || pos[y].empty()) lstans = 1e9;
else if (x == y) lstans = 0;
else {
if (pos[x].size() > pos[y].size()) swap(x, y);
if (pos[x].size() <= B) lstans = solvebf(x, y);
else lstans = bans[y][x], debug(">(y = %d, x = %d, t = %d)", y, x, t);
}
if (lstans > n) cout << "yyb is our red sun and zsy is our blue moon" << endl, lstans = 0;
else cout << lstans << endl;
}
}
return 0;
}
\(O(n\sqrt n)\)
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
typedef long long LL;
constexpr int B = 300;
int n, m, a[100010], id[100010], bcnt, mp[100010];
vector<int> P[100010];
vector<int> bans[100010 / B + 10];
void rebuild(int b) {
if (!id[b]) id[b] = ++bcnt;
int u = id[b];
bans[u].assign(1e5 + 1, 1e9);
for (int i = 1, len = 1e9; i <= n; i++) {
if (a[i] == b)
len = 0;
else
bans[u][a[i]] = min(bans[u][a[i]], ++len);
}
for (int i = n, len = 1e9; i >= 1; i--) {
if (a[i] == b)
len = 0;
else
bans[u][a[i]] = min(bans[u][a[i]], ++len);
}
P[b].clear();
}
void modify(int &x, int& y) {
if (x == y || !x) return ;
if (!y) return y = x, x = 0, void();
if (id[x] && !id[y]) swap(x, y);
for (int i = 1; i <= bcnt; i++) bans[i][y] = min(bans[i][y], bans[i][x]);
if (id[x]) {
for (int i = 1; i <= n; i++)
if (a[i] == x) a[i] = y;
P[x].clear();
rebuild(y);
} else {
for (int p : P[x]) a[p] = y;
vector<int> tmp;
merge(P[x].begin(), P[x].end(), P[y].begin(), P[y].end(),
back_inserter(tmp));
P[x].clear(), P[y] = tmp;
if (P[y].size() > B) rebuild(y);
}
x = 0;
}
int query(int x, int y) {
if (x == y && (id[x] || !P[x].empty())) return 0;
int ans = 1e9;
if (id[x]) ans = min(ans, bans[id[x]][y]);
if (id[y]) ans = min(ans, bans[id[y]][x]);
vector<int> tmp;
merge(P[x].begin(), P[x].end(), P[y].begin(), P[y].end(), back_inserter(tmp));
for (int i = 0; i + 1 < (int)tmp.size(); i++)
if (a[tmp[i]] != a[tmp[i + 1]]) ans = min(ans, tmp[i + 1] - tmp[i]);
return ans;
}
int main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i], P[a[i]].push_back(i), mp[a[i]] = a[i];
for (int c = 0; c <= 1e5; c++)
if (P[c].size() > B) rebuild(c);
while (m--) {
static int lst = 0;
int op, x, y;
cin >> op >> x >> y;
#ifdef ONLINE_JUDGE
x ^= lst, y ^= lst;
#endif
if (op == 1) {
modify(mp[x], mp[y]);
} else {
lst = query(mp[x], mp[y]);
if (lst > n) cout << "Ikaros" << endl, lst = 0;
else cout << lst << endl;
}
}
return 0;
}