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

每个位置有很多种放字符的方法，把初始的字符也离线下来，同时作为操作一起排序。

考虑到不管什么位置，我只要排过一遍序，后来者一定比先覆盖上去的严格不劣，所以直接进行区间覆盖单点查询即可。

代码实现细节的话也没啥好说的，就是无脑堆板子就好了。

时间复杂度 $O(n\log n)O(n\backslash log\; 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) 2e5 + 5;
int a[N], L[N << 2], R[N << 2], Rlx[N << 2];
void build(int root, int l, int r){
	L[root] = l, R[root] = r;
	if (l == r) { Rlx[root] = 0; return; }
	int mid = (l + r) >> 1;
	build(root << 1, l, mid), build(root << 1 | 1, mid + 1, r);
	Rlx[root] = 0;
}
int mx(int x, int y){
	return x > y ? x : y;
}
void pushdown(int root){
	Rlx[root << 1] = mx(Rlx[root << 1], Rlx[root]);
	Rlx[root << 1 | 1] = mx(Rlx[root << 1 | 1], Rlx[root]);
}
int search(int root, int id){
	int nL = L[root], nR = R[root];
	if (nL == nR) return Rlx[root];
	int mid = (nL + nR) >> 1;
	pushdown(root);
	if (id <= mid) return search(root << 1, id);
	return search(root << 1 | 1, id);
}
void rebuild(int root, int l, int r, int x){
	int nL = L[root], nR = R[root];
	if (l <= nL && nR <= r) { Rlx[root] = mx(Rlx[root], x); return; }
	int mid = (nL + nR) >> 1;
	pushdown(root);
	if (l <= mid) rebuild(root << 1, l, r, x);
	if (r >= mid + 1) rebuild(root << 1 | 1, l, r, x);
}
struct Node{
	int l, r, c;
	friend bool operator<(const Node&p, const Node&q){
		return p.c < q.c;
	}
}s[N];
signed main(){
	int n = init(), m = init();
	int sLen = 0;
	for (int i = 1; i <= n; ++i) {
		char c = getchar();
		while (c < 33 || c > 126)
			c = getchar();
		s[++sLen] = (Node) {i, i, (int)c};
	}
	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); // 排序
	build(1, 1, n); // 堆一个线段树板子
	for (int i = 1; i <= sLen; ++i)
		rebuild(1, s[i].l, s[i].r, s[i].c); // 区间推平
	int ans = 0;
	for (int i = 1; i <= n; ++i)
		ans += search(1, i); // 单点查询
	print(ans), putchar('\n');
}