牛客练习赛C魔法学院(hard version) 并查集加速

练习赛C魔法学院(hard version) 并查集加速"/>

牛客练习赛C魔法学院(hard version) 并查集加速

题目

给出一个小写字母字符串，现在有m种魔法，每种魔法可以将区间LR的字母变为新字母X，求最后字符串的最大字典序。

题解思路

两种比较容易想到的操作：

1. 将操作按照X的大小从小到大排序，每次暴力区间覆盖即可，可以使用客珂朵莉树。
2. 将操作按照X的大小从大到小排序，相同区间覆盖一次，之后不再覆盖，可以用并查集加速跳跃过程。

并查集代码

#include <bits/stdc++.h>
using namespace std;const int N = 1e7 + 5;char s[N];
struct node
{int l, r;char f[2];bool operator<(const node &temp) const { return f[0] > temp.f[0]; }
} op[N];int fa[N];int find(int x)
{if (x == fa[x])return x;return fa[x] = find(fa[x]);
}
void solve()
{int n, m;scanf("%d %d", &n, &m);for (int i = 1; i <= n + 1; i++)fa[i] = i;scanf("%s", s + 1);for (int i = 1; i <= m; i++)scanf("%d %d %s", &op[i].l, &op[i].r, op[i].f);sort(op + 1, op + 1 + m);for (int i = 1; i <= m; i++){for (int j = op[i].l; j <= op[i].r; j = find(j + 1)){// cout << '\t' << j << endl;s[j] = max(s[j], op[i].f[0]);fa[j] = j + 1;}}int ans = 0;for (int i = 1; i <= n; i++)ans += s[i];printf("%d\n", ans);
}int main()
{solve();return 0;
}