P5692 手牵手走向明天

2023-10-16 12:36:10

P5692 手牵手走向明天

有一个长度为 \(n\) 的序列 \(a\)，有 \(m\) 次操作。

给定 \(l,r,x,y\)，将 \(a_l,a_{l+1},a_{l+2},\cdots,a_r\) 中等于 \(x\) 的数全部改成 \(y\)。
给定 \(l,r,x,y\)，找到 \(i,j\) 满足 \(i,j\in[l,r]\) 且 \(a_i=x,a_j=y\)，并要求 \(|i-j|\) 最小，求这个最小值，无解输出 -1。

\(1 \leq n,m,a_i\leq 10^5\)，时限 \(1.50\text{s}\)，空限 \(512\text{MB}\)。

sol

「弑尽破净第四分块」加强版。

无难度评分。

相较于 P5397 天降之物，这题是对区间修改和查询，所以我们不能再用原先的值域分块。

考虑序列分块。

对于答案在一个块内的情况显然可以预处理。

但这里如果是开一个 \(dis[i][j][k]\) 的三维数组的话空间是 \(n^2\sqrt n\) 级别的。

注意到每个块内只有 \(\sqrt n\) 个数，所以可以使用类似于离散化的技巧，对于每个数，把它映射到一个标号，这样空间就是 \(n\sqrt n\) 开得下了，可 \(\mathcal O(1)\) 获取⼀个数在某个块中的标号，\(dis[i][j][k]\) 的定义为第 \(i\) 个块内，数 \(j\) 与离散化后的 \(k\) 的最短距离。

如果不在一个块内的话，，由于我们要求距离最⼩，那么每个块中可能成为答案的，只有这个数第⼀次出现的位置和最后⼀次出现的位置，维护每个块内每个数第一次和最后一次出现的位置，然后扫一遍，维护 \(x\) 和 \(y\) 各自最后一次出现的位置即可，单次时间复杂度 \(\mathcal O(\sqrt n)\)。

对于散块的查询直接扫过去，单次时间复杂度为 \(\mathcal O(\sqrt n)\)。

再看修改，枚举每一个块，假设一个块中最开始有 \(m\) 个颜色，那么修改 \(x\) 为 \(y\)：

无 \(x\)：跳过。
有 \(x\) 无 \(y\)：改标号即可。
有 \(x\) 有 \(y\)：对于 \(x,y\) 以外的 \(m-2\) 个颜色，每一个颜色都需要进行 \(\mathcal O(1)\) 次修改，然后合并 \(x,y\) 的颜色信息也是 \(\mathcal O(m)\) 的，总时间复杂度是 \(O(m)\)，并且每次操作完 \(m\) 减少一。

考虑怎么更新 \(dis\) 数组的信息，容易想到，枚举每个其他颜色，取 \(\min\) 即可。

那么一个块最多产生多少次操作？

因为 \(m\) 最大为 \(\sqrt{n}\) ，所以一个块中的操作次数其实是 \(\mathcal O(n)\) 级别的，所以总操作次数就是 \(O(n\sqrt{n})\)。

最后看散块修改，最大的问题在于关于 \(y\) 的距离怎么修改，因为做的是 \(\min\)，直接修改似乎不好办。

考虑到，先用 \(O(\sqrt{n})\) 的代价将这一块的 \(a_i\) 的实际值求出来，然后对于 \(y\) 的相关信息直接求一遍，\(x\) 的相关信息也直接求一遍，这一部分的复杂度是 \(O(\sqrt{n})\) 的。

需要注意的是，散块的修改可能增加一个颜色，但是散块最多只会增加 \(\sqrt n\) 个颜色，所以时间复杂度还是对的。

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

\(\text{2.76s / 398.59MB / 6.84KB C++98 O2}\)。

#include <cstdio>
#include <cmath>
#include <cstring>

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
#endif

inline 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');
}

const int N = 1e5 + 3, S = 3e2 + 3, T = 6e2 + 3, inf = 0x3f3f3f3f;

int n, m, q, a[N];

int sqrtn, bl[N], L[T], R[T];

int dis[T][S][S], disl[T][S], disr[T][S], pot[T][N], rpot[T][S], lim[T];

int rt[T][S], col[N], fa[N];

int find(int x)
{
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

inline int min(int x, int y)
{
	return x < y ? x : y;
}

inline int max(int x, int y)
{
	return x > y ? x : y;
}

inline void chkmin(int &x, int y)
{
	x = min(x, y);
}

inline void chkmax(int &x, int y)
{
	x = max(x, y);
}

inline void swap(int &x, int &y)
{
	x ^= y ^= x ^= y;
}

inline void upd_dis(int t, int _L, int _R, int y)
{
	int tl = -inf;
	const int &py = pot[t][y];
	for (int j = _L; j <= _R; ++j)
	{
		if (col[find(j)] == y)
			tl = j;
		chkmin(dis[t][py][pot[t][col[find(j)]]], j - tl);
		chkmin(dis[t][pot[t][col[find(j)]]][py], j - tl);
	}
	tl = inf;
	for (int j = _R; j >= _L; --j)
	{
		if (col[find(j)] == y)
			tl = j;
		chkmin(dis[t][py][pot[t][col[find(j)]]], tl - j);
		chkmin(dis[t][pot[t][col[find(j)]]][py], tl - j);
	}
}

inline void init()
{
	sqrtn = sqrt(n * 2.2 / 5);
	for (int i = 1, c = 1, j; i <= n; i = j + 1, ++c)
	{
		L[c] = i, R[c] = j = min(n, i + sqrtn);
		for (int t = L[c]; t <= R[c]; ++t)
			bl[t] = c;
	}
	m = bl[n];
	memset(disl, 60, sizeof disl);
	memset(disr, -61, sizeof disr);
	memset(dis, 60, sizeof dis);
	for (int t = 1; t <= m; ++t)
	{
		for (int i = L[t]; i <= R[t]; ++i)
		{
			if (!pot[t][a[i]])
			{
				rpot[t][pot[t][a[i]] = ++lim[t]] = a[i];
				col[rt[t][lim[t]] = i] = a[i];
			}
			fa[i] = rt[t][pot[t][a[i]]];
		}
		for (int i = L[t]; i <= R[t]; ++i)
			if (fa[i] == i)
				upd_dis(t, L[t], R[t], a[i]);
		for (int i = R[t]; i >= L[t]; --i)
			disl[t][pot[t][a[i]]] = i;
		for (int i = L[t]; i <= R[t]; ++i)
			disr[t][pot[t][a[i]]] = i;
	}
}

inline int calc(int l, int r, int x, int y)
{
	int ans = inf, lx = -inf, ly = -inf;
	for (int i = l; i <= r; ++i)
	{
		if (col[find(i)] == x)
			lx = i, chkmin(ans, i - ly);
		if (col[find(i)] == y)
			ly = i, chkmin(ans, i - lx);
	}
	return ans;
}

inline int query(int l, int r, int x, int y)
{
	if (x == y)
	{
		bool flag = 0;
		if (bl[l] == bl[r])
			for (int i = l; i <= r; ++i)
				flag |= col[find(i)] == x;
		else
		{
			for (int i = l; i <= R[bl[l]]; ++i)
				flag |= col[find(i)] == x;
			for (int i = L[bl[r]]; i <= r; ++i)
				flag |= col[find(i)] == x;
			for (int i = bl[l] + 1; i <= bl[r] - 1; ++i)
				flag |= pot[i][x] > 0;
		}
		return -1 + flag;
	}
	if (bl[l] == bl[r])
		return calc(l, r, x, y);
	int ans = min(calc(l, R[bl[l]], x, y), calc(L[bl[r]], r, x, y));
	int lx = disr[bl[l]][pot[bl[l]][x]];
	if (lx < l)
		lx = -inf;
	int ly = disr[bl[l]][pot[bl[l]][y]];
	if (ly < l)
		ly = -inf;
	for (int i = bl[l] + 1; i <= bl[r] - 1; ++i)
	{
		if (pot[i][x])
			chkmin(ans, disl[i][pot[i][x]] - ly);
		if (pot[i][y])
			chkmin(ans, disl[i][pot[i][y]] - lx);
		if (pot[i][x])
			lx = disr[i][pot[i][x]];
		if (pot[i][y])
			ly = disr[i][pot[i][y]];
		chkmin(ans, dis[i][pot[i][x]][pot[i][y]]);
	}
	int rx = disl[bl[r]][pot[bl[r]][x]];
	if (rx > r)
		rx = inf;
	int ry = disl[bl[r]][pot[bl[r]][y]];
	if (ry > r)
		ry = inf;
	return min(ans, min(rx - ly, ry - lx));
}

inline void deleted(int t, int px)
{
	const int &lt = lim[t];
	swap(rt[t][px], rt[t][lt]);
	for (int i = 1; i <= lt; ++i)
		swap(dis[t][px][i], dis[t][lt][i]), swap(dis[t][i][px], dis[t][i][lt]);
	swap(disl[t][px], disl[t][lt]), swap(disr[t][px], disr[t][lt]);
	swap(rpot[t][px], rpot[t][lt]), swap(pot[t][rpot[t][px]], px), --lim[t];
}

inline void cg(int t, int l, int r, int x, int y)
{
	int ret = 0, &px = pot[t][x], &py = pot[t][y];
	const int &_L = L[t], &_R = R[t];
	for (int i = l; i <= r; ++i)
		ret += col[find(i)] == x;
	if (!ret)
		return;
	if (!py)
	{
		rpot[t][py = ++lim[t]] = y, disl[t][py] = inf, disr[t][py] = -inf;
		for (int i = 1; i <= lim[t]; ++i)
			dis[t][py][i] = dis[t][i][py] = inf;
	}
	for (int i = 1; i <= lim[t]; ++i)
		dis[t][px][i] = dis[t][i][px] = inf;
	for (int i = _L; i <= _R; ++i)
	{
		a[i] = col[find(i)];
		rt[t][pot[t][a[i]]] = 0;
	}
	for (int i = l; i <= r; ++i)
		if (a[i] == x)
		{
			a[i] = y;
			--ret;
		}
	for (int i = _L; i <= _R; ++i)
		ret += a[i] == x;
	if (!ret)
		deleted(t, px);
	for (int i = _L; i <= _R; ++i)
	{
		if (!rt[t][pot[t][a[i]]])
			col[rt[t][pot[t][a[i]]] = i] = a[i];
		fa[i] = rt[t][pot[t][a[i]]];
	}
	upd_dis(t, _L, _R, y);
	if (ret)
		upd_dis(t, _L, _R, x);
	for (int i = _R; i >= _L; --i)
		disl[t][pot[t][a[i]]] = i;
	for (int i = _L; i <= _R; ++i)
		disr[t][pot[t][a[i]]] = i;
	if (!ret)
		px = 0;
}

inline void modify(int l, int r, int x, int y)
{
	if (x == y)
		return;
	if (bl[l] == bl[r])
		return cg(bl[l], l, r, x, y), void();
	cg(bl[l], l, R[bl[l]], x, y);
	cg(bl[r], L[bl[r]], r, x, y);
	for (int t = bl[l] + 1; t <= bl[r] - 1; ++t)
	{
		int &px = pot[t][x], &py = pot[t][y];
		if (!px)
			continue;
		if (!py)
		{
			rpot[t][py = px] = y, px = 0, col[rt[t][py]] = y;
			continue;
		}
		fa[rt[t][px]] = rt[t][py], rt[t][px] = 0;
		for (int i = lim[t]; i >= 1; --i)
		{
			chkmin(dis[t][py][i], dis[t][px][i]);
			chkmin(dis[t][i][py], dis[t][i][px]);
		}
		chkmin(disl[t][py], disl[t][px]);
		chkmax(disr[t][py], disr[t][px]);
		for (int i = lim[t]; i >= 1; --i)
			dis[t][px][i] = dis[t][i][px] = inf;
		deleted(t, px), px = 0;
	}
}

int op, l, r, x, y;

int main()
{
	n = read(), q = read();
	for (int i = 1; i <= n; ++i)
		a[i] = read();
	init();
	for (int i = 1; i <= q; ++i)
	{
		op = read(), l = read(), r = read(), x = read(), y = read();
		if (op == 1)
			modify(l, r, x, y);
		else
		{
			int ans = query(l, r, x, y);
			write(ans > n ? -1 : ans);
			putchar('\n');
		}
	}
}

码农公寓

P5692 手牵手走向明天

sol

相关文章