自动搬运

查看原文

来自洛谷，原作者为

	ForgetOIDuck 私宅一个，毙了

搬运于2025-08-24 23:10:24，当前版本为作者最后更新于2025-06-23 21:29:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

为了这道题特意学了在收藏夹里吃灰三年的主席树。

题意

有 $m$ 个长度为 $n$ 的序列 $a_i$。给定 $a_1$，并且 $\forall2\le i\le m$ 都满足 $a_i$ 与 $a_{i-1}$ 只在一个位置上不同，且给定不同位置及对应 $a_i$ 的值。求这 $m$ 个序列按字典序排序后的序列编号。

思路

最朴素想法肯定是把每个序列单独抠出来排序。问题在于一大堆数如何比较两个序列 $i, j$ 字典序大小。

都朴素到这个地步了你就别想着暴力比较了。我们使用一种叫做二$\tiny{分}$哈$\tiny{希}$的东西，二分一个位置 $p$ 比对 $i,j$ 两个哈希 $[1,p]$ 部分是否不同，借此可以找到第一个不一样的地方，然后就可以比大小了；若是超出去了就说明两个相等了，比较 $i,j$ 本身数值大小即可。

把每个序列抠出来是 $O(mn)$ 的，排序加上比较函数本身复杂度是 $O(m \log m \log n)$ 的。预处理前缀哈希值的空间也是 $O(mn)$ 的。

这样你就获得了一份 $O($ 不能过 $)$ 的优秀代码。

想想是否有什么条件被我们漏掉了：那当然是相邻两个序列之间只有一个不同！我们想到了主席树的优秀性质：每次只改一个点，只动一条链，便不需要把每个序列及其哈希抠出来；而前缀哈希甚至是区间哈希刚好可以使用线段树轻松维护，我们就高兴地过掉了这道题。

时间复杂度 $O((n+m)\log n+m\log m\log n)$，毫无卡常必要。

一些细节：

• 不仅要存哈希值也要存原来数组的值，找到不同位置后需要比较原来值的大小。

• 空间需要开到 $2\times 10^7$。

• 为防止卡哈希需要使用一些不常见的模数及基数。

• 开着 long long 总没坏处。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll n, m, a[500002], rt[500002], idx = 1, pw[500002], ans[500002];
struct tree{
	ll x, hs, ls, rs;
}tr[20000002];
void build(ll x, ll l, ll r) {
	if (l == r) return tr[x] = {a[l], a[l] * pw[n - l] % mod, 0, 0}, void(0);
	ll mid = l + r >> 1;
	tr[x].ls = ++ idx, build(idx, l, mid);
	tr[x].rs = ++ idx, build(idx,mid+1,r);
	tr[x].hs = (tr[tr[x].ls].hs + tr[tr[x].rs].hs) % mod;
}
ll update(ll x, ll l, ll r, ll p, ll c) {
	if (l == p && r == p) return tr[++ idx] = {c, c * pw[n - l] % mod, 0, 0}, idx;
	ll mid = l + r >> 1, t;
	if (mid >= p) return t = update(tr[x].ls, l, mid, p, c), tr[++ idx] = {0, (tr[t].hs + tr[tr[x].rs].hs) % mod, t, tr[x].rs}, idx;
	if (mid <  p) return t = update(tr[x].rs,mid+1,r, p, c), tr[++ idx] = {0, (tr[tr[x].ls].hs + tr[t].hs) % mod, tr[x].ls, t}, idx;
}
ll query(ll lx, ll rx, ll l, ll r) {
	if (l == r) return tr[lx].hs == tr[rx].hs ? 2 : (tr[lx].x < tr[rx].x);
	ll mid = l + r >> 1;
	if (tr[tr[lx].ls].hs != tr[tr[rx].ls].hs) return query(tr[lx].ls, tr[rx].ls, l, mid);
	return query(tr[lx].rs, tr[rx].rs,mid+1,r);
}

bool cmp(ll az, ll bz) {
	ll t = query(rt[az], rt[bz], 1, n);
	if (t == 2) return az < bz;
	return t;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0); 
	pw[0] = 1;
	cin >> n >> m;
	ll bs = 131; 
	rt[1] = 1;
	for (ll i = 1; i <= n; i ++ ) pw[i] = pw[i - 1] * bs % mod, cin >> a[i];
	build(1, 1, n);
	for (ll i = 1; i <= m; i ++ ) ans[i] = i;
	for (ll i = 2, p, x; i <= m; i ++ ) cin >> p >> x, rt[i] = update(rt[i - 1], 1, n, p, x);
	sort(ans + 1, ans + m + 1, cmp);
	for (ll i = 1; i <= m; i ++ ) cout << ans[i] << (i == m ? "\n" : " ");
}