NC229102. 魔法学院(hard version)
描述
本题与easy version唯一的区别在于数据范围不同。
亚可喜欢上了收集不包括空格的可见字符(ASCII码为33~126)，在她眼中，一个字符的价值为其ASCII码大小，比如’a’的价值为97。
目前她已经收集了个不包括空格的可见字符，第
个字符为
。可是她想要把自己收集的
个字符的价值和最大化，因此去请求了戴安娜的帮助。
戴安娜有种魔法，第
种魔法可以将
区间的一个字符替换为
。因为戴安娜出色的魔力，所以每种魔法都可以使用无限次。
请问戴安娜使用完若干次魔法后，亚可收集的个字符的最大价值和可以是多少？
输入描述
第一行两个正整数
,
，其中：
,
。
第二行一个长度为
。
接下来
,
和一个不包括空格的可见字符
，满足
。
输出描述
输出使用完若干次魔法后的最大价值和。
示例1
输入:
3 3 aaa 1 3 b 2 3 c 3 3 d
输出:
297
C++ 解法, 执行用时: 579ms, 内存消耗: 217048K, 提交时间: 2021-11-13 12:48:34
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>R[127];
int fa[10000005]={0};
char c,S[10000005];
int find(int a)
{
if(a==fa[a])return a;
return fa[a]=find(fa[a]);
}
int main()
{
int i,j,k,l,r,n,m,ans=0;
scanf("%d%d%s",&n,&m,S+1);
for(i=1;i<=n;i++)fa[i]=i;
while(m--)
{
scanf("%d%d %c",&l,&r,&c);
R[c].push_back({l,r});
}
for(i=126;i>=33;i--)
for(j=0;j<R[i].size();j++)
{
l=R[i][j].first,r=R[i][j].second;
for(k=find(r);k>=l;k=find(k))S[k]=max(S[k],(char)i),fa[k]=find(k-1);
}
for(i=1;i<=n;i++)ans+=S[i];
printf("%d\n",ans);
return 0;
}