题解 | #魔法学院#

BC用优先队列做的（大概是数据不够强偷鸡了）。

思路比较好理解：提前对左端点排序，对于某个点保证所有可行的修改方法都在优先队列内。那么只要到一个新的点判断优先队列里的队头元素是否还适用于当前点，如果不行一直pop；可行就不管（贪就完事了）。

复杂度算不明白我就不算了。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e7+10;
const int M = 1e6+10;
int n,m;
char a[N];
struct node{
    int l,r;
    char c;
    bool operator<(const node& tmp) const {
        return c < tmp.c;
    }
}maj[M];

bool cmp(const node a,const node b){
    return a.l < b.l;
}

void print(__int128 x)
{
    if(x < 0)
    {
        x = -x;
        putchar('-');
    }
     if(x > 9) print(x/10);
    putchar(x%10 + '0');
}

int main(){
//     cout << 1ll*1e7*126 << endl;
    scanf("%d %d",&n,&m);
    scanf("%s",a+1);
    for(int i=0;i<m;i++){
        scanf("%d %d %c",&maj[i].l,&maj[i].r,&maj[i].c);
    }
    sort(maj,maj+m,cmp);
//     for(int i=0;i<m;i++){
//         printf("%d %d %c\n",maj[i].l,maj[i].r,maj[i].c);
//     }
    priority_queue<node> pq;
    int cur = 0;
    __int128 sum = 0;
    for(int i=1;i<=n;i++){
        while(!pq.empty()){
            auto x = pq.top();
            if(x.r < i) pq.pop();
            else break;
        }
        while(cur < m && maj[cur].l <= i){
            pq.push(maj[cur]);
            cur++;
        }
        if(!pq.empty()){
            if(a[i] < pq.top().c){
                a[i] = pq.top().c;
            }
        }
        sum += (int)a[i];
    }
    print(sum);
    return 0;
}