传送门

背景

这是本蒟蒻校内模拟赛的一道题，模拟赛打废了。

思路

前置

可持久化线段树，字典序比较，哈希。

字典序比较

我们先来看看如何比较 $s1$ 和 $s2$ 这两个字符串的字典序（$len_{s1} = len_{s2}$）。一个朴素的想法是我们逐位比较，直到得出结果，时间复杂度是 $O(len)$。

for(int i = 0;i < len;i++){
    if(s1[i] != s2[i]){
        if(s1[i] < s2[i]) cout << "s1 is small.";
        else cout << "s2 is small.";
        break;
    }
}

容易想到，我们可以利用 hash 加二分的思路来优化逐位比较，即二分找到 $s1$ 和 $s2$ 的最长相同的前缀，并比较它们，时间复杂度 $O(\log len)$

for(int i = 1;i <= len;i++){
    hs1[i] = hs1[i - 1] * hs + s1[i - 1] - 'a' + 1;
    hs2[i] = hs2[i - 1] * hs + s2[i - 1] - 'a' + 1;
}
// 预处理 s1 和 s2 的 hash 数组
int l = 1, r = len, ans = 0;
while(l <= r){
    int mid = (l + r) / 2;
    if(hs1[mid] == hs2[mid]) l = mid + 1, ans = mid;
    else r = mid - 1;
}
if(s1[ans] < s2[ans]) cout << "s1 is small.";
else cout << "s2 is small.";

如何维护数组 hash 值

我们已经知道怎样经行字典序比较了，那如何快速地求出当前状态的 hash 值呢？

由于暴力开数组一定会炸，而我们又发现每次修改只有一个点，故我们可以考虑开一个可持久化线段树来维护每个状态的 hash 值即可。

二分加优化

经过上文的一通乱搞，我们得到了时间复杂度为 $O(m \times \log^2 n)$ 的代码，可还是会超时，怎么办呢？

我们有一个小优化，注意到我们的二分其实可以放在线段树上进行，当左子树不同时查左子树，相同则查右子树，时间复杂度 $O(m \times \log n)$，于是我们通过了此题。

代码

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int maxn = 1000010;
const int inf = 1e9;
const int hs = 1e9 + 7;// 或 1331
//unsigned long long 
//cout << fixed << setprecision(3)
//cout << setw(5) << 
//continue
int n, m, a[maxn], t, p[maxn];
struct S{
	int ls, rs, sum;
}f[maxn * 20];
struct S1{
	int id, sum;
}g[maxn];
void up(int u, int l, int r){
	int mid = (l + r) / 2;
	f[u].sum = f[f[u].ls].sum * p[r - mid] + f[f[u].rs].sum;
}
void build(int u, int l, int r){
	if(l == r) f[u].sum = a[l];
	else{
		int mid = (l + r) / 2;
		f[u].ls = ++t;
		build(f[u].ls, l, mid);
		f[u].rs = ++t;
		build(f[u].rs, mid + 1, r);
		up(u, l, r);
	}
}
void add(int u, int u1, int l, int r, int id, int sum){
	f[u] = f[u1];
	if(l == r) f[u].sum = sum;
	else{
		int mid = (l + r) / 2;
		if(id <= mid){
			f[u].ls = ++t;
			add(f[u].ls, f[u1].ls, l, mid, id, sum);
		}else{
			f[u].rs = ++t;
			add(f[u].rs, f[u1].rs, mid + 1, r, id, sum);
		}
		up(u, l, r);
	}
}
int q(int u, int u1, int l, int r){
	if(l == r){
		if(f[u].sum == f[u1].sum) return -1;
		return f[u].sum < f[u1].sum;
	}else{
		int mid = (l + r) / 2;
		if(f[f[u].ls].sum != f[f[u1].ls].sum) return q(f[u].ls, f[u1].ls, l, mid);
		else return q(f[u].rs, f[u1].rs, mid + 1, r);
	}
}
bool cmp(S1 a, S1 b){
	int d = q(a.sum, b.sum, 1, n);
	if(d == -1) return a.id < b.id;
	return d;
}
signed main(){
    // freopen("sort.in", "r", stdin);
    // freopen("sort.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    p[0] = 1;
    for(int i = 1;i <= n;i++){
    	cin >> a[i];
    	p[i] = p[i - 1] * hs;
    }
    g[1].sum = ++t;
    g[1].id = 1;
    build(g[1].sum, 1, n);
    for(int i = 2;i <= m;i++){
    	int p, x;
    	cin >> p >> x;
    	g[i].sum = ++t;
    	g[i].id = i;
    	add(g[i].sum, g[i - 1].sum, 1, n, p, x);
    }
    sort(g + 1, g + 1 + m, cmp);
    for(int i = 1;i <= m;i++) cout << g[i].id << ' ';
    return 0;
}

感谢阅读！