题解 | #魔法学院2hard#

想了很久，主席树，差分什么的，感觉根本行不通，这题其实感觉来源于洛谷P4145花神游历各国，我好惭愧，想到做法时已经写不完了。 很容易想到的就是，我们把所有修改用结构体存起来，并按照字符从大到小排序，那么一个点如果最多只需要被最大的那个字符修改一次，我们可以，也就是说对于一次修改，我们只需要修改区间[l, r]中没有被修改过的点就可以了，我们就可以用并查集来加速找没有被修改过的点这个过程，一个点被修改过，我们直接跳过去就行了 当i这个点没有被修改过时，fa[i] = i， 当i被修改过之后，令fa[i] = i + 1(当前点右边相邻点可能就是下一个需要修改点), 以(i+1)号点为起点，寻找下一个需要被修改的点的位置，也就是说在[l, r]不断找fa[i] = i的点

#include <bits/stdc++.h>

using namespace std;
 
#define sz(X) ((int)(X).size())
#define fi first
#define se second
#define pb push_back
#define rep(i, a, n) for (int i = a; i <= n; i ++ ) 
#define per(i, a, n) for (int i = n; i >= a; i -- )
#define mst memset
#define endl '\n'
#define si(x) scanf("%d", &x)
#define sll(x) scanf("%lld", &x)
#define pi(x) printf("%d\n", x)
#define pll(x) printf("%lld\n", x)
#define sc scanf
#define pr printf
#define IO ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);

using ll = long long;
using i64 = unsigned long long;

constexpr int N = 1e7 + 10;
int n, m, fa[N];
char c[N];
string s;
struct node {
    int l, r;
    char op;
    bool operator < (const node &cmp) const {
        return op > cmp.op;
    }
}a[N];

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void solve() {
    cin >> n >> m;
    cin >> s;
    rep(i, 1, m) {
        cin >> a[i].l >> a[i].r >> a[i].op;
    } 
    rep(i, 1, n ) {
        fa[i] = i;
    }
    fa[n + 1] = n + 1;
    sort(a + 1, a + m + 1);
    rep(i, 1, m) {
        int l = a[i].l, r = a[i].r;
        while (l <= r) {
            c[l] = max(c[l], a[i].op);//修改这个点
            fa[l] = l + 1;//以下一个点为起点寻找
            l = find(fa[l]);//找下一个fa[i] = i的点
        }
    }
    int ans = 0;
    rep(i, 1, n) {
        ans += max((int)s[i - 1], (int)c[i]);//统计答案，没啥好说的把
    }
    cout << ans << '\n';
}

signed main(void) {
    IO;
	int t;
	t = 1;
	while (t -- ) {
		solve();
	}
    return 0;
}
``