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

根据题目意思很容易就能明白，就是给一个序列，然后有 $mm$ 次区间修改，把区间$[l,r][l,r]$ 内比 $cc$ 小的数全部改成 $cc$ ，最后求出序列的和。

第一眼看过去貌似线段树就可以水过去，然后写了半小时思路混乱放弃了（线段数还是学的太拉了）。

于是再仔细思考一下，它貌似只有一次查询，又不那么像线段树了，于是再稍微思考一下，顿时就悟了，这不是差分的水题吗（自己还是太菜了

只要从136开始到33，这之间的数全部搞一次差分，不就得到了值最大的序列吗

献上代码：

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
const int N = 1e5 +7;

int n, m;
string s;
vector<pair<int, int> > num[200];  //记录136到33之间每个字母出现的区间
bool vis[N];	//从大到小遍历136到33，所以改过的字母一定是最大的，就不用改了，加个标记
int sum[N];		//差分数组

void solve() {
    cin >> n >> m >> s; 
    s = ' ' + s;
    int l, r; char c;
    for(int i = 1; i <= m; ++ i) {
        cin >> l >> r >> c;
        num[c].push_back({l, r});
    }
  
    for(int i = 136; i >= 33; -- i) {
        if(num[i].size() == 0) continue;
        for(int j = 0; j <= n; ++ j) sum[j] = 0;
      
        for(int j = 0; j < num[i].size(); ++ j) 
            sum[num[i][j].first] ++, sum[num[i][j].second + 1] --;
      
        for(int j = 1; j <= n; ++ j) {
            sum[j] += sum[j - 1];
            if(vis[j]) continue;
            if(sum[j] > 0) {
                s[j] = max(s[j], char(i));
                vis[j] = 1;
            }
        }
      
    }
  
    int ans = 0;
    for(int i = 1; i <= n; ++ i) ans += s[i];
    cout << ans << endl;
}

signed main() { ios;
    int t = 1; //cin >> t;
    while(t --) solve();
}
```