C-魔法学院(hard version)

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

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

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

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

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

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

第一行两个正整数 $n$ , $m$ ，其中： $n\leq 10^{7}$ , $m\leq 10^{6}$ 。

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

接下来 $m$ 行，每行两个正整数 $l_{i}$ , $r_{i}$ 和一个不包括空格的可见字符 $c_{i}$ ，满足 $l_{i}\leq r_{i} \leq n$ 。

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

示例1

复制

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

复制