魔法学院

题目描述：

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

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

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

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

思路1: 差分 + 贪心

对于每个字符，我们更新他能影响的所有的点的答案，最后计算所以点的答案和即可

方法是差分前缀和，搞一个差分数组d，++d[l],--d[r + 1]，然后前缀和加起来，如果sum[i] > 0则说明这个点会被该字符影响到，更新这个点的答案就行

复杂度是 O(94 * n)

能解决easy版本，但是对于hard版本就不行了

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m;
int l, r;
char p;
vector<pii>tr[200];
int ans[MAX];
int d[200050];

void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> p;
        ans[i] = (int)p;
    }
    for(int i = 1; i <= m; ++i){
        cin >> l >> r >> p;
        tr[(int)p].push_back(m_p(l, r));
    }
    for(int i = 33; i <= 126; ++i){
        mem(d, 0);
        for(auto [l, r] : tr[i]){
            ++d[l];--d[r + 1];
        }
        for(int j = 1; j <= n; ++j){
            d[j] += d[j - 1];
            if(d[j])ans[j] = max(ans[j], i);
        }
    }
    ll sum = 0;
    for(int i = 1; i <= n; ++i)sum += ans[i];
    cout << sum << endl;
}


int main(){
    io;
    work();
    return 0;
}

思路2:贪心 + 线段树区间覆盖

我们可以把字符串的每个字符拆成一个[i, i]的区间，和输入的m个区间放在一起，按照价值从小到大的顺序排序，然后开始区间覆盖，不难发现这样的贪心显然正确

复杂度O((n + m)log(n))

也是只能过easy版本，过不了hard版本

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ls p<<1
#define rs p<<1|1
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

//不改范围见祖宗!!!
#define MAX 500000 + 50
int n, m, k, op;

struct ran{
    int l, r, val;
    bool operator <(const ran &x)const{
        return val < x.val;
    }
}ar[MAX];

ll sum[MAX];
int la[MAX];

inline void pushup(int p){
    sum[p] = sum[ls] + sum[rs];
}

inline void built(int p, int l, int r){
    if(l == r){
        sum[p] = la[p] = 0;
        return;
    }
    int mid = (l + r) / 2;
    built(ls, l, mid);
    built(rs, mid + 1, r);
    pushup(p);
}

inline void cal_lazy(int p, int len, int x){
    la[p] = x;
    sum[p] = 1ll * len * x;
}

inline void pushdown(int p, int len){
    if(la[p]){
        cal_lazy(ls, len - len / 2, la[p]);
        cal_lazy(rs, len / 2, la[p]);
        la[p] = 0;
    }
}

inline void update(int p, int l, int r, int s, int t, int x){
    if(l >= s && t >= r){
        cal_lazy(p, r - l + 1, x);
        return;
    }
    pushdown(p, r - l + 1);
    int mid = (l + r) / 2;
    if(mid >= s)update(ls, l, mid, s, t, x);
    if(mid < t)update(rs, mid + 1, r, s, t, x);
    pushup(p);
}

inline ll getsum(int p, int l, int r, int s, int t){
    if(l >= s && t >= r){
        return sum[p];
    }
    pushdown(p, r - l + 1);
    ll sum = 0;
    int mid = (l + r) / 2;
    if(mid >= s)sum += getsum(ls, l, mid, s, t);
    if(mid < t)sum += getsum(rs, mid + 1, r, s, t);
    return sum;
}

void work(){
    cin >> n >> m;
    char p;
    for(int i = 1; i <= n; ++i){
        cin >> p;
        ar[i].l = ar[i].r = i;
        ar[i].val = (int)p;
    }
    for(int i = 1; i <= m; ++i){
        cin >> ar[i + n].l >> ar[i + n].r;
        cin >> p;
        ar[i + n].val = (int)p;
    }
    sort(ar + 1, ar + 1 + m + n);
    built(1, 1, n);
    for(int i = 1; i <= n + m; ++i){
        update(1, 1, n, ar[i].l, ar[i].r, ar[i].val);
    }
    cout << getsum(1, 1, n, 1, n) << endl;
}


int main(){
    work();
    return 0;
}

思路3: 贪心 + 并查集

先不管那个字符串，直接将m个区间按照价值从大到小的顺序排好，对于高价值字符覆盖过的区间，低价值字符就没有必要去遍历了，所以我们可以使用并查集来解决

最后再用每一位的最大值和字符串的对应位置比大小，取最大的，求和

复杂度是：O(max(n, mlogm))

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m;
char p;
char c[MAX];
int fa[MAX];
inline int getfa(int x){
    return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}
struct ran{
    int l, r, p;
}tr[MAX];
bool cmp(ran a, ran b){
    return a.p > b.p;
}
int ans[MAX];
void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)cin >> c[i];
    for(int i = 1; i <= m; ++i){
        cin >> tr[i].l >> tr[i].r >> p;
        tr[i].p = (int)(p);
    }
    for(int i = 1; i <= n + 1; ++i)fa[i] = i;
    sort(tr + 1, tr + 1 + m, cmp);
    for(int i = 1; i <= m; ++i){
        auto [l, r, z] = tr[i];
        l = getfa(l);
        while (l <= r) {
            ans[l] = max(ans[l], z);
            fa[l] = l + 1;
            l = getfa(l + 1);
        }
    }
    ll cnt = 0;
    for(int i = 1; i <= n; ++i){
        cnt += max(ans[i], (int)c[i]);
    }
    cout << cnt << endl;
}


int main(){
    io;
    work();
    return 0;
}

思路4：珂朵莉树 + “玄学优化”

和方法2的思路差不多，但是方法2用线段树只去进行区间覆盖就很浪费时间，而珂朵莉树可以很好的处理区间覆盖问题

但是有一点需要注意，不要像方法2的线段树一样把字符串的每个点一起处理了，如果一起处理了，可能会导致珂朵莉初始的大小是n，就会T，解决方法就是在最后统计答案的时候便利珂朵莉树的set的每个区间的每个数，和字符串对应位置的数值取一个最大值，求和就行

复杂度是O(能过)

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define it set<ran>::iterator
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 20000000 + 50
int n, m;
int l, r;
vector<pii>s[130];
char ss[MAX];
struct ran{
    int l, r;
    mutable int val;
    ran(int L, int R = -1, int Val = 0){
        l = L;r = R;val = Val;
    };
    bool operator <(const ran &x)const{
        return l < x.l;
    }
};
set<ran>tr;

it split(int pos){
    if(pos > n)return tr.end();
    it itt = tr.lower_bound(pos);
    if(itt != tr.end() && itt->l == pos)return itt;
    --itt;
    int l = itt->l, r = itt->r, v = itt->val;
    tr.erase(itt);
    tr.insert(ran(l, pos - 1, v));
    return tr.insert(ran(pos, r, v)).first;
}

void emerge(int l, int r, int v){
    it itr = split(r + 1), itl = split(l);
    tr.erase(itl, itr);
    tr.insert(ran(l, r, v));
}

ll getans(){
    ll ans = 0;
    for(auto [l, r, v] : tr){
        for(int i = l; i <= r; ++i){
            ans += max(v, (int)ss[i]);
        }
    }
    return ans;
}

void work(){
    scanf("%d%d", &n, &m);
    scanf("%s", ss + 1);
    tr.insert(ran(1, n, 0));
    for(int i = 1; i <= m; ++i){
        char p[3];
        scanf("%d%d", &l, &r);
        scanf("%s", p);
        s[(int)p[0]].push_back(m_p(l, r));
    }
    for(int i = 33; i <= 126; ++i){
        for(auto [l, r] : s[i]){
            emerge(l, r, i);
        }
    }
    printf("%lld\n", getans());
}


int main(){
    work();
    return 0;
}