牛客练习赛91 魔法学院(hard version) 并查集 双向链表

牛客练习赛91 魔法学院(hard version) 并查集 双向链表

牛客练习赛91 魔法学院(hard version) 并查集 双向链表

题目链接：

题目描述：

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

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

戴安娜有m种魔法，第i种魔法可以将 [ l i , r i ] [l_i,r_i] [li​,ri​]区间的一个字符替换为 c i c_i ci​。因为戴安娜出色的魔力，所以每种魔法都可以使用无限次。

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

输入描述：

第一行两个正整数n,m，其中：n ≤ 1 0 7 10^7 107 m ≤ 1 0 6 10^6 106。第二行一个长度为n且由不包括空格的可见字符组成的字符串S。接下来m行，每行两个正整数 l i , r i l_i, r_i li​,ri​和一个不包括空格的可见字符 c i c_i ci​，满足 l i ≤ r i ≤ n l_i≤r_i≤n li​≤ri​≤n。

输出描述：

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

题解：

对于每个给定的区间，按字符 c i c_i ci​排序，从大到小地对字符串S进行覆盖，这样在覆盖完后，这段区间就是最高价值了，在之后就无需遍历了，时间复杂度 O ( n ) O(n) O(n)。我们可以使用双向链表进行跳跃式地遍历 [ l i , r i ] [l_i,r_i] [li​,ri​]这段区间，在找 l i l_i li​时因为不清楚 l i l_i li​是否已经被删除，所以用并查集找到离 l i l_i li​最近的靠右的未被删除节点，在某个节点 i 被删除时，只需要将 f a [ i ] = i + 1 fa[i] = i+1 fa[i]=i+1 即可。

代码：

#include<bits/stdc++.h>
using namespace std;const int N = 1e7+5, M = 1e6+5;int n, m;
typedef long long ll;
ll ans;
char s[N];
struct Dota { // 存放每个区间int l, r, x;bool operator < (const Dota & a) const {return x < a.x;}
}dota[M];int fa[N]; // 并查集
inline int find(int x) {if(fa[x] == -1) return x;return fa[x] = find(fa[x]);
}struct Node { // 双向链表int l, r, x;
}node[N];int main() {scanf("%d%d", &n, &m);scanf("%s", s+1);char t[5];for(int i=1; i <= m; i++) {scanf("%d%d%s", &dota[i].l, &dota[i].r, t);dota[i].x = (int)t[0];   }sort(dota+1, dota+1+m); for(int i=1; i <= n; i++) { fa[i] = -1;node[i].l = i-1;node[i].r = i+1;node[i].x = (int)s[i];ans += (ll)s[i]; // 将初始字符串S的价值计入答案}fa[n+1] = -1;node[0].r = 1;node[n+1].l = n;for(int i=m; i >= 1; i--) { // 从大到小地进行覆盖int l = dota[i].l, r = dota[i].r, x = dota[i].x;int p = find(l); // 找到离l最近的靠右的未被删除节点while(p <= r) { // 遍历整个区间if(node[p].x <= x)ans = ans - (ll)node[p].x + (ll)x;int L = node[p].l, R = node[p].r;node[L].r = R;node[R].l = L;fa[p] = p+1; // 删除节点时要通过并查集更新每个点最近的靠右的未被删除节点p=node[p].r; // 移动到下一个节点}}printf("%lld", ans);return 0;
}