P5397 天降之物

P5397 天降之物

给定一个长为 n n n 的序列 a a a，有 m m m 次操作。

把序列中所有值为 x x x 的数的值变成 y y y。找出一个位置 i i i 满足 a i = x a_i=x ai​=x，找出一个位置 j j j 满足 a j = y a_j=y aj​=y，使得 ∣ i − j ∣ |i-j| ∣i−j∣ 最小，并输出 ∣ i − j ∣ |i-j| ∣i−j∣。

1 ≤ n , m , a i ≤ 1 0 5 1 \leq n,m,a_i\leq 10^5 1≤n,m,ai​≤105，时限 500 ms 500\text{ms} 500ms，空限 256 MB 256\text{MB} 256MB。

sol

「弑尽破净第四分块」。

难度评分： 6 6 6。

先分析一下题意，由于这里修改和查询都是全局的，所以并不需要序列分块。

考虑从值域入手，对每一个值维护一个下标集合，支持合并集合，查询两集合中差值最小的下标。

先考虑两种暴力做法：

预处理每一个值离其他所有值的最短距离，从前到后扫一遍，再从后到前扫一遍，可做到 O ( n ) \mathcal O(n) O(n) 的实现。对于修改，直接 O ( n ) \mathcal O(n) O(n) 暴力重构；查询 O ( 1 ) \mathcal O(1) O(1) 查询。维护每一个值的所有位置，修改就把整个位置集合合并，查询就暴力枚举位置。

这显然会时空爆炸，考虑用根号分治来平衡两种暴力的复杂度。

具体来讲可以把数分为出现次数大于根号的和小于等于根号次的，我们分别称其为大数和小数。

然后首先可以想到维护每个数的出现位置，这样对于查询两个小数的情况可以直接线性归并得到结果，单次复杂度 O ( n ) \mathcal O(\sqrt n) O(n ​)。

接着对于大数，因为它最多只有根号个，所以可以考虑用第一种方法，对每个大数预处理其对于其它所有数的答案，正反扫两次序列即可，预处理时间复杂度 O ( n ) \mathcal O(n) O(n)，单次查询时间复杂度 O ( 1 ) \mathcal O(1) O(1)。

再看修改，有三种情况：

小数小数合并，结果是小数就不管，大数就暴力更新，单次时间复杂度为 O ( n ) \mathcal O(\sqrt n) O(n ​)。

大数大数合并仍然是暴力更新，因为每个大数最多被合并一次，所以单次时间复杂度仍然是 O ( n ) \mathcal O(\sqrt n) O(n ​)。

一个小数和一个大数的合并，如果每次往一个大数里面合并一个大小为一的小数每次都暴力跑就炸掉了，所以考虑优化。我们可以考虑给每个大数再维护一个集合，里面仍然储存当前数的一些出现位置，不过需要保证其大小不超过 n \sqrt n n ​。我们可以在合并时把小数放进大数的集合里面，等到集合大小超过 n \sqrt n n ​ 时再去暴力跑一次答案。那这时我们对大数预处理出的答案就有了新的定义，即“该数不在集合内的元素和其他数的答案”。最后在查询时只需要单独处理一下集合内元素的贡献即可，单次时间复杂度为 O ( n ) \mathcal O(\sqrt n) O(n ​)。

所以总时间复杂度为 O ( ( n + m ) n ) \mathcal O((n+m)\sqrt{n}) O((n+m)n ​)，总空间复杂度为 O ( n n ) \mathcal O(n\sqrt n) O(nn ​)。

7.27s/124.45MB/5.36KBC++20O2 \text{7.27s / 124.45MB / 5.36KB C++20 O2} 7.27s/124.45MB/5.36KBC++20O2。

#include <cstdio>#include <cmath>#include <cstring>#include <vector>namespace Fread{const int SIZE = 1 << 21;char buf[SIZE], *S, *T;inline char getchar(){if (S == T){T = (S = buf) + fread(buf, 1, SIZE, stdin);if (S == T)return '\n';}return *S++;}}namespace Fwrite{const int SIZE = 1 << 21;char buf[SIZE], *S = buf, *T = buf + SIZE;inline void flush(){fwrite(buf, 1, S - buf, stdout);S = buf;}inline void putchar(char c){*S++ = c;if (S == T)flush();}struct NTR{~NTR(){flush();}} ztr;}#ifdef ONLINE_JUDGE#define getchar Fread::getchar#define putchar Fwrite::putchar#endifinline int read(){int x = 0, f = 1;char c = getchar();while (c < '0' || c > '9'){if (c == '-')f = -1;c = getchar();}while (c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}return x * f;}inline void write(int x){if (x < 0){putchar('-');x = -x;}if (x > 9)write(x / 10);putchar(x % 10 + '0');}inline int max(int x, int y){return x > y ? x : y;}inline int min(int x, int y){return x < y ? x : y;}const int N = 100007, M = 320, inf = 0x3f3f3f3f;int n, m, a[N], lastans;int lim, siz[N], ans[M][N], id[N], F[N], tot;std::vector<int> v[N];inline void build(int x, int Id = 0){id[x] = Id ? Id : ++tot;int t = id[x];memset(ans[t], 0x3f, sizeof ans[t]);for (int i = 1, j = inf; i <= n; ++i)if (a[i] == x)j = 0;elseans[t][a[i]] = min(ans[t][a[i]], ++j);for (int i = n, j = inf; i; --i)if (a[i] == x)j = 0;elseans[t][a[i]] = min(ans[t][a[i]], ++j);std::vector<int> ddd;ans[t][x] = 0, v[x].swap(ddd);}inline void merge(int x, int y){int i = 0, j = 0, sx = v[x].size(), sy = v[y].size();std::vector<int> res;while (i < sx && j < sy)res.push_back(v[x][i] < v[y][j] ? v[x][i++] : v[y][j++]);while (i < sx)res.push_back(v[x][i++]);while (j < sy)res.push_back(v[y][j++]);v[y] = res;}inline int merge_(int x, int y){int i = 0, j = 0, sx = v[x].size(), sy = v[y].size(), res = inf;if (!sx || !sy)return inf;while (i < sx && j < sy)res = min(v[x][i] < v[y][j] ? v[y][j] - v[x][i++] : v[x][i] - v[y][j++], res);if (i < sx)res = min(res, abs(v[x][i] - v[y][sy - 1]));if (j < sy)res = min(res, abs(v[x][sx - 1] - v[y][j]));return res;}inline int query(int x, int y){x = F[x], y = F[y];if (!siz[x] || !siz[y])return -1;if (x == y)return 0;if (siz[x] > siz[y])x ^= y ^= x ^= y;if (siz[y] <= lim)return merge_(x, y);else if (siz[x] <= lim)return min(ans[id[y]][x], merge_(x, y));elsereturn min(merge_(x, y), min(ans[id[x]][y], ans[id[y]][x]));}inline void change(int x, int y){int x_ = F[x], y_ = F[y];if (!siz[x_] || x_ == y_)return;if (siz[x_] > siz[y_])F[y] = x_, F[x] = n + 1, x_ ^= y_ ^= x_ ^= y_;elseF[x] = n + 1;if (x_ > n || y_ > n)return;x = x_, y = y_;if (siz[y] <= lim){if (siz[x] + siz[y] <= lim){for (int i : v[x])a[i] = y;for (int i = 1; i <= tot; ++i)ans[i][y] = min(ans[i][y], ans[i][x]);merge(x, y);}else{for (int i = 1; i <= n; ++i)if (a[i] == x)a[i] = y;build(y);}}else if (siz[x] <= lim){if (siz[x] + v[y].size() <= lim){for (int i : v[x])a[i] = y;for (int i = 1; i <= tot; ++i)ans[i][y] = min(ans[i][y], ans[i][x]);merge(x, y);}else{for (int i = 1; i <= n; ++i)if (a[i] == x)a[i] = y;build(y, id[y]);}}else{for (int i = 1; i <= n; ++i)if (a[i] == x)a[i] = y;build(y, id[y]);}std::vector<int> clea;siz[y] += siz[x], siz[x] = 0, v[x].swap(clea);}signed main(){n = read(), m = read(), lim = sqrt(n);for (int i = 1; i <= n; ++i)++siz[a[i] = read()], v[a[i]].push_back(i), F[i] = i;for (int i = 0; i <= n; ++i)if (siz[i] > lim)build(i);while (m--){int opt = read(), x = read() ^ lastans, y = read() ^ lastans;if (opt == 1)change(x, y);else{lastans = query(x, y);if (~lastans)write(lastans), putchar('\n');elselastans = 0, putchar('I'), putchar('k'), putchar('a'), putchar('r'), putchar('o'), putchar('s'), putchar('\n');}}return 0;}