[Ynoi2018] 天降之物
这个根号分治太神啦。
首先考虑一个朴素的暴力：对每个数维护出现位置的 std::vector 这样查询可以两个指针遍历 std::vector 做到平方复杂度。
注意到复杂度和出现次数有关，那么就可以考虑阈值分治了，然而合并的操作使得我们不好维护信息。
先考虑不带修的情况，对于每个大数维护这个数到其它数的答案，总复杂度为 \(O(\dfrac{n^2}{B})\)。小数暴力做，大数直接查询答案，就可以做到 \(O(n \sqrt n)\)。这个是比较简单的。
现在考虑修改怎么做。假设 \(x\) 的出现次数小于等于 \(y\) 的出现次数，暴力的想法是每次合并两个数就直接重构，这样子的话只要一直把出现次数为 \(1\) 的数合并到出现次数为 \(O(n)\) 的数就可以卡成 \(O(n^2)\) 了，寄。
但是我们注意到如果合并的两个数都是大数，上面的做法就是对的了。因为这样的重构次数是 \(O(\dfrac{n}{B})\) 的。那么就只需考虑小数的合并。
考虑一个“缓冲”的想法，就是对每个 \(x\) 开一个 std::vector，相当于加入 \(x\) 的数的懒标记，当这个 std::vector 大小超过 \(B\) 时就重构，查询时可以直接对懒标记做暴力。这样懒标记之间的合并的总复杂度是 \(O(nB)\) 的，重构次数是 \(O(\dfrac nB)\) 的。总复杂度 \(O(n \sqrt n)\)
做来做去这么多其实就是一个懒标记的思想。难想但挺有意思的。
#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
using namespace std;
typedef long long LL;
namespace IO {
#define isdigit(x) (x >= '0' && x <= '9')
template<typename T>
inline void read(T &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
if(f) x = -x;
}
template<typename T>
inline void write(T x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
#undef isdigit
}
using namespace IO;
const int N = 1e5 + 10;
const int B = 500;
int n, m, a[N];
vector<int> vec[N];
int ans[N / B + 10][N];
inline void ckmin(int &x, int y) {
y < x ? x = y : 0;
}
int id[N], t = 0;
void build(const int x) {
if(!id[x]) id[x] = ++t;
const int u = id[x];
for(int i = 1; i <= n; ++i)
ans[u][i] = N;
for(int i = 1, k = N; i <= n; ++i) {
if(a[i] == x) k = 0;
ckmin(ans[u][a[i]], k++);
}
for(int i = n, k = N; i >= 1; --i) {
if(a[i] == x) k = 0;
ckmin(ans[u][a[i]], k++);
}
vector<int>().swap(vec[x]);
}
void modify(int &x, int &y) {
if(x == y || !x) return ;
if(!y) return y = x, x = 0, void();
if(id[x]) swap(x, y);
for(int i = 1; i <= t; ++i)
ckmin(ans[i][y], ans[i][x]);
if(id[x]) {
for(int i = 1; i <= n; ++i)
if(a[i] == x) a[i] = y;
build(y);
} else {
for(int i : vec[x]) a[i] = y;
vector<int> tmp(sz(vec[x]) + sz(vec[y]));
merge(vec[x].begin(), vec[x].end(),
vec[y].begin(), vec[y].end(),
tmp.begin());
vec[y] = tmp;
if(sz(vec[y]) > B) build(y);
}
vector<int>().swap(vec[x]), x = 0;
}
int query(const int x, const int y) {
if(!x || !y) return -1;
if(x == y) return 0;
int res = N;
auto i = vec[x].begin(), j = vec[y].begin();
const auto ex = vec[x].end(), ey = vec[y].end();
int lx = -N, ly = -N;
while(i != ex || j != ey) {
if(j != ey && (i == ex || *j < *i)) ckmin(res, (ly = *j) - lx), j++;
else ckmin(res, (lx = *i) - ly), i++;
}
if(id[x]) ckmin(res, ans[id[x]][y]);
if(id[y]) ckmin(res, ans[id[y]][x]);
return res;
}
int main() {
read(n), read(m);
static int mp[N];
for(int i = 1; i <= n; ++i)
read(a[i]), vec[a[i]].emplace_back(i), mp[a[i]] = a[i];
for(int i = 1; i <= n; ++i)
if(sz(vec[i]) > B) build(i);
for(int i = 1, lst = 0; i <= m; ++i) {
int op, x, y;
read(op), read(x), read(y);
x ^= lst, y ^= lst;
if(op == 1)
modify(mp[x], mp[y]);
else {
lst = query(mp[x], mp[y]);
if(~lst) printf("%d\n",lst);
else puts("Ikaros"), lst = 0;
}
}
return 0;
}