魔法学院(hard version)5

魔法学院(hard version)5

魔法学院(hard version)

题号：NC229102
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述 

本题与easy version唯一的区别在于数据范围不同。

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

目前她已经收集了nn个不包括空格的可见字符，第ii个字符为S_{i}Si​。可是她想要把自己收集的nn个字符的价值和最大化，因此去请求了戴安娜的帮助。

戴安娜有mm种魔法，第ii种魔法可以将[l_{i},r_{i}][li​,ri​]区间的一个字符替换为c_{i}ci​。因为戴安娜出色的魔力，所以每种魔法都可以使用无限次。

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

输入描述:

第一行两个正整数nn,mm，其中：nleq 10^{7}n≤107,mleq 10^{6}m≤106。

第二行一个长度为nn且由不包括空格的可见字符组成的字符串SS。

接下来mm行，每行两个正整数l_{i}li​,r_{i}ri​和一个不包括空格的可见字符c_{i}ci​，满足l_{i}leq r_{i} leq nli​≤ri​≤n。

输出描述:

输出使用完若干次魔法后的最大价值和。

示例1

输入

复制

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

输出

复制

297

思路：之前想用差分，但是发现好像不好用，一般数字操作上的差分，每一次的操作是直接在上一次操作的基础上操作的，但是这个题目的变换，每次不是单纯的加上或者减去（tmp-a），那个数是不确定的，可能之前这一段里有的数之前有det但操作后，det变为0了，诶这个是突破口，但是还得是最大的，还不知道每次的操作顺序和次数。