题解 | #魔法学院(hard version)#

接着上一篇题解的分析过程，我们还是考虑把操作离线下来看看怎么搞一搞。

注意到我们可以更改排序的 cmp 顺序，原来是从小权值到大权值，这是为了方便进行区间推平。

现在我们换过来，从大权值到小权值，这样做的好处就是保证每个位置至多被修改一次，链表维护一下下一个被修改的位置就好了。

时间复杂度 $O(n)O(n)$。

#include<cstdio>
#include<algorithm>
#define int long long
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 1e6 + 5;
struct Node{
	int l, r, c;
	friend bool operator<(const Node&p, const Node&q){
		return p.c > q.c;
	}
}s[N];
const int M = (int) 1e7 + 5;
char str[M];
int nxt[M], vis[M];
signed main(){
	int n = init(), m = init();
	for (int i = 1; i <= n; ++i)
		while (str[i] < 33 || str[i] > 126)
			str[i] = getchar();
	int sLen = 0;
	for (int i = 1; i <= m; ++i) {
		int l = init(), r = init();
		char c = getchar();
		while (c < 33 || c > 126)
			c = getchar();
		s[++sLen] = (Node) {l, r, (int)c};
	}
	std::stable_sort(s + 1, s + 1 + sLen);
	for (int i = 0; i <= n; ++i)
		nxt[i] = i + 1, vis[i] = 0;
	vis[n + 1] = 0;
	int ans = 0;
	for (int i = 1; i <= sLen; ++i) {
		int l = s[i].l, r = s[i].r, c = s[i].c;
		for (int i = l; i <= r;)
			if (!vis[i]) {
                int j = nxt[i];
				vis[i] = c, nxt[i] = nxt[r], ++ans;
                i = j;
            }
            else i = nxt[i];
		if (ans == n) break;
	}
	int sum = 0;
	for (int i = 1; i <= n; ++i)
		if (vis[i] > (int) str[i]) sum += vis[i];
        else sum += (int) str[i];
	print(sum), putchar('\n');
}