题目描述

亚可喜欢上了收集不包括空格的可见字符(ASCII码为33~126)，在她眼中，一个字符的价值为其ASCII码大小，比如’a’的价值为97。

目前她已经收集了n个不包括空格的可见字符，第i个字符S[i]。可是她想要把自己收集的nn个字符的价值和最大化，因此去请求了戴安娜的帮助。戴安娜有m种魔法，第i种魔法可以将[l[i],r[i]]区间的一个字符替换为c[i]。因为戴安娜出色的魔力，所以每种魔法都可以使用无限次。

请问戴安娜使用完若干次魔法后，亚可收集的n个字符的最大价值和可以是多少？

输入样例

3 3
aaa
1 3 b
2 3 c
3 3 d

输出样例

297

算法

(并查集) O(玄学时间复杂度)O(玄学时间复杂度)

其实这一题与 牛客练习赛91_D 的第二种方法基本上相同,AcWing题解戳这里,牛客题解戳这里 在这里我们使用并查集来记录每个点的"后一个应该被访问的点是哪个",因为我们在这里与easy版本一样是根据c[i]进行了排序，那么我就保证了每个点只会被修改一次 并查集操作

for(int i=1;i<N;i++) f[i]=i;//用f[i]来记录下一个要更改的点
for(int i=0;i<m;i++)
{
    int l=e[i].l,r=e[i].r,c=e[i].c;;
    while(l<=r)
    {
        st[l]=max(st[l],(char)e[i].c);
        f[l]=l+1;//下一个
        l=find(f[l]);
    }
}

这题真的太容易超时了，加上牛客的测评机也不是很稳定所以我用了快读和快输出

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=1e7+10;
int f[N],n,m;
char st[N];
typedef long long ll;
struct node
{
    int l,r,c;
    bool operator<(const node &w)const
    {
        return c>w.c;
    }
}e[N];

void print(ll x)  
{  
    int num = 0; char c[15];
    while(x) c[++num] = (x%10)+48, x /= 10;
    while(num) putchar(c[num--]);
    putchar('\n'); 
}

void get(int &x)
{
    char c = getchar(); x = 0;
    while(c < '0' || c > '9') c = getchar();
    while(c <= '9' && c >= '0') x = x*10+c-48, c = getchar();
}

int find(int x)
{
    if(x!=f[x])
        f[x]=find(f[x]);
    return f[x];
}

int main()
{
    cin>>n>>m;
    getchar();
    for(int i=1;i<=n;i++)
    {
        char t;
        t=getchar();
        st[i]=t;
    }
    for(int i=0;i<m;i++)
    {
        get(e[i].l);
        get(e[i].r);
        char t;
        t=getchar();
        e[i].c=(int)t;
    }
    sort(e,e+m);
    for(int i=1;i<N;i++) f[i]=i;//用f[i]来记录下一个要更改的点
    for(int i=0;i<m;i++)
    {
        int l=e[i].l,r=e[i].r,c=e[i].c;;
        while(l<=r)
        {
            st[l]=max(st[l],(char)e[i].c);
            f[l]=l+1;//下一个
            l=find(f[l]);
        }
    }
    ll sum=0;
    for(int i=1;i<=n;i++) sum+=(int)st[i];
    print(sum);
}