牛客练习赛91BC 魔法学院(线段树/差分/并查集加速暴力)

线段树/差分/并查集加速暴力)"/>

牛客练习赛91BC 魔法学院(线段树/差分/并查集加速暴力)

B题，数据范围1e5，范围较小。
区间修改，区间查询，很明显的线段树+懒标记板子,套一块模板即可

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, w[N];struct node {int l, r;int sum, add;
} tr[4 * N];void pushup(int u) {tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}void pushdown(int u) {auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];if (root.add) {left.add = max(root.add, left.add);right.add = max(root.add, right.add);root.add = 0;}}void build(int u, int l, int r) {if (l == r) {tr[u] = {l, r, w[r], 0};} else {tr[u] = {l, r};int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);}
}void modify(int u, int l, int r, int d) {if (tr[u].l >= l && tr[u].r <= r) {tr[u].add = max(d, tr[u].add);} else {pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if (l <= mid)modify(u << 1, l, r, d);if (r > mid)modify(u << 1 | 1, l, r, d);pushup(u);}
}int query(int u, int l, int r) {if (tr[u].l == tr[u].r) {return max(tr[u].sum,tr[u].add);}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;int sum = 0;if (l <= mid)sum = query(u << 1, l, r);if (r > mid)sum += query(u << 1 | 1, l, r);return sum;
}int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {char ch;cin >> ch;w[i] = ch;}build(1, 1, n);while (m--) {int l, r;char ch;cin >> l >> r >> ch;int k = ch;modify(1, l, r, k);}cout << query(1, 1, n) << endl;
}

也可以用类差分+优先队列的方法来做,将覆盖区间的左右端点打上标记，当我们从左到右扫描时遇到开始标记，就将这个标记纳入优先队列，同时设个数组进行标记，当遇到结束标记时，就将这个魔法在标记数组中减1，同时，如果优先队列的顶部的标记消失了，就需要弹出。

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef pair<int, int>PII;
const int N = 1e5 + 10;
int n, m;
int st[200];//哪些是捏在手里的
priority_queue <char, vector<char>, less<char> >q; //现在正在用哪些东西在扫
char a[N];vector<char>gett[N], lose[N];void solve() {cin >> n >> m;for (int i = 1; i <= n; i++) {char ch;cin >> a[i];}while (m--) {int l, r;char ch;cin >> l >> r >> ch;gett[l].push_back(ch);lose[r + 1].push_back(ch);}int ans = 0;for (int i = 1; i <= n; i++) {for (auto j : gett[i]) {q.push(j);st[j]++;}for (auto j : lose[i]) {st[j]--;while (q.size() && st[q.top()] == 0) {q.pop();}}if (q.size())a[i] = max(a[i], q.top());ans += a[i];}cout << ans << endl;}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();
}

C题，数据范围1e7，线段树和差分都会爆空间，考虑用并查集加速:
将所有魔法按优先级sort一下，然后暴力填涂，如果已经被涂过了就利用并查集跳到未填涂的地方，否则就在填涂该格后并查集指向区间的右端

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
int n, m;
const int N = 1e7 + 10;int f[N];//指向一个区间里的主线
struct node {char val;int l, r;
} q[N];
char a[N];bool cmp(node a, node b) {if (a.val == b.val) {return a.l < b.l;}return a.val > b.val;
}int find(int x) {return x == f[x] ? f[x] : find(f[x]);
}void solve() {cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];f[i] = i;}for (int i = 1; i <= m; i++) {cin >> q[i].l >> q[i].r >> q[i].val;}sort(q + 1, q + 1 + m, cmp);for (int i = 1; i <= m; i++) {int l = q[i].l, r = q[i].r;char ch = q[i].val;if(find(l)>r)continue;for (int i = l; i <= r; i++) {i = find(i);if (i > r)break;f[i] = max(f[i], r);a[i] = max(a[i], ch);}}int ans = 0;for (int i = 1; i <= n; i++) {ans += a[i];}cout << ans << endl;}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();
}