题解 | #智乃的数字积木(hard version)#

智乃的数字积木(hard version)

https://ac.nowcoder.com/acm/contest/23478/F

F、智乃的数字积木(hard version)

启发式合并，每次选较小的颜色往大的块上面并。

具体来讲，这道题要维护若干个颜色相同的“块”。

alt

对于每一个块，其实并不需要每一次都暴力排序，其实我们只需要知道其中有几个1，几个2，几个3...

使用桶排序的思路统计每个块中数字的个数。

然后它一定是形如一个99..9988..8877..7766..6655..5544..4433...的形式，可以拆解成若干个连续相同的数字。

比如9999887766=9999*1000000+88*10000+77*100+66。

这个东西它等于 $(10^n-1)\times \frac{m}{9}$ ，其中 $n$ 是位数， $m$ 是构造的数字。

有了这种数学方法，我们就可以快速求一个块在全局ans中提供的答案是多少，见std代码中的calc::部分。

然后现在的需求就是设计一种数据结构维护一个全局的ans，全局ans=每个块的答案之和。

对于这种维护一个全局答案的题目不用每次都全部求一边，只需要在修改时先减去原本的贡献，然后修改后再加回来即可，也就是说通过维护该变量的形式而不是每次都求解。

接下来的问题在于，每次染色后如何合并颜色相同的块。

这里设计算法的时候要注意，不要考虑同时合并多个块，只考虑两个块之间的二合并。

因为你一旦陷入思考染色后三个同色块相邻的情况就会继续思考四个五个...

对于染色后需要合并多个色块的情况，都转化为相邻块之间的二合并。

alt

合并色块实际上就是将色块里面的桶中的数字直接相加。见block operator + (const block &A, const block&B)的运算符重载，这个合并可以视为是 $O (1)$ 的。

那么如何枚举颜色相同的块呢，比如现在要讲颜色 $u$ 变为 $v$ 。

这里用到的数据结构应该是一个平衡树或者不定长数组储存相同颜色的块。

这里随便用什么都可以，看自己的喜好，这里使用平衡树维护实际上就是用std::set维护，不定长数组实际上就是用std::vector。

用set在查找的时候可以用自带的二分查找，比较方便，而且保证插入的时候有序，缺点就是这样写总体复杂度为 $O (N l o g^{2} N)$ 。

然后接下来每次合并的时候暴力枚举相同颜色的块。

问题来了，如何保证每次暴力枚举颜色相同色块的时间复杂度？

这里就用到启发式合并了，即每一次暴力枚举颜色时，取维护色块颜色 $u$ 和颜色 $v$ 的数据结构尺寸较小的那个暴力插入到另一个当中，然后清空该数据结构。

假设色块的总数为 $N$ 则每次暴力合并的总时间复杂度为 $O (N l o g N)$ ，均摊到每次操作的均摊复杂度就是 $O (l o g N)$ 。

这个时间复杂度计算的方法是：考虑暴力插入的次数，每次合并结束后，较小尺寸数据结构的尺寸都会至少翻倍，那么每一个元素的暴力插入次数就会小于 $l o g N$ 次，所以总复杂度就是 $N l o g N$ 。

然后就是一些小细节的处理可以使用并查集维护。

时间复杂度 $O (N l o g N)$ ，空间复杂度 $O (N)$ 。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXM = 100005;
const int MAX_CNT = 10;
const long long mod = 1e9 + 7;
const long long inv9 = 111111112;
namespace calc {
long long pow10[MAXN];
void init(int n)
{
	pow10[0] = 1;
	for (int i = 1; i <= n; ++i)
	{
		pow10[i] = pow10[i - 1] * 10 % mod;
	}
}
//11111111               base=1, len=8
//2222222222             base=2, len=10
//333333333333333        base=3, len=15
long long make_number(long long base, long long len)
{
	long long ret = (pow10[len] - 1) * inv9 % mod * base % mod;
	if (ret < 0)ret += mod;
	return ret;
}
}
long long ans;
int col_to_id[MAXM], id_to_col[MAXM];
vector<int> col_blocks[MAXM];
int n, m, k, fa[MAXN * 2], col[MAXN], u, v;
char s[MAXN];
int findf(int x)
{
	return x == fa[x] ? x : fa[x] = findf(fa[x]);
}
void unions(int x, int y)
{
	if (findf(x) != findf(y))
	{
		fa[findf(x)] = findf(y);
	}
	return;
}
struct block
{
	int l, r;
	int col_id;
	int cnt[MAX_CNT];
	bool enable;
	long long get_val()
	{
		long long ret = 0;
		for (int i = 9; ~i; --i)
		{
			long long temp = calc::make_number(i, cnt[i]);
			ret = ret * calc::pow10[cnt[i]] % mod;
			ret += temp;
			ret %= mod;
		}
		ret *= calc::pow10[n - r];
		ret %= mod;
		return ret;
	}
};
block operator + (const block &A, const block&B)
{
	block C;
	C.l = min(A.l, B.l);
	C.r = max(A.r, B.r);
	C.col_id = A.col_id;
	C.enable = true;
	for (int i = 0; i < MAX_CNT; ++i)
	{
		C.cnt[i] = A.cnt[i] + B.cnt[i];
	}
	return C;
}
vector<block>b;
void dsu_init()
{
	for (int i = 1; i <= n * 2; ++i)
	{
		fa[i] = i;
	}
}
void init_block()
{
	int cnt[MAX_CNT];
	for (int l = 1, r = 1; l <= n; l = r + 1, r = l)
	{
		while (r < n && col[r + 1] == col[l])++r;
		memset(cnt, 0, sizeof(cnt));
		for (int i = l; i <= r; ++i)
		{
			cnt[s[i] - '0']++;
			unions(i, n + 1 + b.size());
		}
		block current_block;

		current_block.l = l;
		current_block.r = r;
		current_block.col_id = col_to_id[col[l]];
		current_block.enable = true;
		memcpy(current_block.cnt, cnt, sizeof(cnt));
		col_blocks[col[l]].push_back(b.size());
		b.push_back(current_block);

	}
}
void init_ans()
{
	ans = 0;
	for (auto i : b)
	{
		ans += i.get_val();
		if (ans >= mod)ans -= mod;
	}
	return;
}
void modify_ans(long long val, long long op)
{
	ans += val * op;
	ans = (ans % mod + mod) % mod;
}
void init_col()
{
	for (int i = 1; i <= m; ++i)
	{
		col_to_id[i] = i;
		id_to_col[i] = i;
	}
}
void vector_merge(vector<int>&V_from, vector<int>&V_to, int t_col_id)
{
	for (auto it : V_from)
	{
		if (!b[it].enable)continue;
		b[it].col_id = t_col_id;
		modify_ans(b[it].get_val(), -1);
		if (b[it].l > 1)
		{
			block &Lblock = b[findf(b[it].l - 1) - n - 1];
			if (Lblock.col_id == t_col_id)
			{
				modify_ans(Lblock.get_val(), -1);
				unions(b[it].l - 1, n + 1 + it);
				b[it] = Lblock + b[it];
				Lblock.enable = false;
				
			}
		}
		if (b[it].r < n)
		{
			block &Rblock = b[findf(b[it].r + 1) - n - 1];
			if (Rblock.col_id == t_col_id)
			{
				modify_ans(Rblock.get_val(), -1);
				unions(b[it].r + 1, n + 1 + it);
				b[it] = b[it] + Rblock;
				Rblock.enable = false;
				
			}
		}
		modify_ans(b[it].get_val(), 1);
		V_to.push_back(it);
	}
	V_from.clear();
}
void modify_col(int col_from, int col_to)
{
	if (col_from == col_to)return;
	int from_id = col_to_id[col_from];
	int to_id = col_to_id[col_to];
	vector<int>&V_from = col_blocks[from_id];
	vector<int>&V_to = col_blocks[to_id];
	int updated_block_vector_id = V_from.size() < V_to.size() ? to_id : from_id;
	int empty_block_vector_id = V_from.size() < V_to.size() ? from_id : to_id;
	if (V_from.size() < V_to.size())
	{
		vector_merge(V_from, V_to, to_id);
	}
	else
	{
		vector_merge(V_to, V_from, from_id);
	}
	col_to_id[col_to] = updated_block_vector_id;
	id_to_col[updated_block_vector_id] = col_to;
	col_to_id[col_from] = empty_block_vector_id;
	id_to_col[empty_block_vector_id] = col_from;
}
int main()
{
	scanf("%d %d %d", &n, &m, &k);
	scanf("%s", s + 1);
	calc::init(n);
	dsu_init();
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d", &col[i]);
	}
	init_col();
	init_block();
	init_ans();
	printf("%lld\n", ans);
	while (k--)
	{
		scanf("%d %d", &u, &v);
		modify_col(u, v);
		printf("%lld\n", ans);
	}
	return 0;
}