题目描述

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

目前她已经收集了n个不包括空格的可见字符，第i个字符S[i]。可是她想要把自己收集的nn个字符的价值和最大化，因此去请求了戴安娜的帮助。戴安娜有m种魔法，第i种魔法可以将[l[i],r[i]]区间的一个字符替换为c[i]。因为戴安娜出色的魔力，所以每种魔法都可以使用无限次。

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

输入样例

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

输出样例

297

算法

(线段树) $O((n+m)log(n+m))O((n+m)log(n+m))$

其实这一题就是根据node里面的c[i]排序,由c[i]从大到小来修改 如何来优化这个过程呢？ 在这里我是这样想的,如果一个区间的最小值都大于等于我的c[i]了我就不需要修改了,否则我就修改这个区间,并且更新区间最小值(其实这里的时间复杂度我是没有算出来的，因为我是先查询区间之后在区间之内进行单点修改，想着随便交一发，然后就过了？？？还只有80ms，如果有人知道原因麻烦给我留言谢谢！)

整理一下线段树的模板 单点修改

void modify(int u, int x, int v)
{
    if (tr[u].l == x && tr[u].r == x) tr[u].v = v;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

单点查询

void modify1(int u, int x, int d)
{
    if (tr[u].l == tr[u].r)
    {
    tr[u].v=max(tr[u].v,d);
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) modify1(u << 1, x, d);
    if (x > mid) modify1(u << 1 | 1, x, d);
    pushup(u);
    }
}

区间查询

node query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r)return tr[u];
    int mid=tr[u].l+tr[u].r>>1;
    node t1,t2;
    node res;
    if(l>mid) return query(2*u+1,l,r);
    else if(r<=mid) return query(2*u,l,r);
    else
    {
        t1=query(2*u,l,r);
        t2=query(2*u+1,l,r);
        pushup(res,t1,t2);
        return res;
    }
}

区间修改(lazy标记，我不会/(ㄒoㄒ)/~~)

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

typedef long long ll;

const int N=1e5+10;

int st[N];
int n,m;
struct node
{
    int l,r,c;
    bool operator<(const node &w)const
    {
        return c>w.c;
    }
}e[N];

struct node1{
    int l, r;
    int v;
}tr[N*4];

void pushup(int u){
    tr[u].v = min(tr[u<<1].v, tr[u<<1|1].v);
}

void build(int u, int l, int r){
    tr[u] = {l, r};
    if(l==r) 
    {
        tr[u].v=st[r];
        return ;
    }
    int mid = l+r >> 1;
    build(u<<1, l, mid), build(u<<1|1, mid+1, r);
}

void modify1(int u, int x, int d)
{
    if (tr[u].l == tr[u].r)
    {
        tr[u].v=max(tr[u].v,d);
    }
    else 
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify1(u << 1, x, d);
        if (x > mid) modify1(u << 1 | 1, x, d);
        pushup(u);
    }
}

void modify(int u, int l, int r, int d)
{
    if(tr[u].v >= d) return;
    if (tr[u].l >= l && tr[u].r <= r)
    {
        for(int i=tr[u].l;i<=tr[u].r;i++)
            modify1(1,i,d);
    }
    else 
    {
        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 x)
{
    if(tr[u].l==tr[u].r) return tr[u].v;
    int mid=tr[u].l+tr[u].r>>1;
    if(x<=mid) return query(2*u,x);
    else return query(2*u+1,x);
}


int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        char t;
        scanf(" %c",&t);
        st[i]=t;
    }
    build(1,1,n);
    for(int i=0;i<m;i++)
    {
        scanf("%d %d",&e[i].l,&e[i].r);
        char t;
        scanf(" %c",&t);
        e[i].c=(int)t;
    }
    sort(e,e+m);
    for(int i=0;i<m;i++)
    {
        modify(1,e[i].l,e[i].r,e[i].c);
    }
    ll sum=0;
    for(int i=1;i<=n;i++) 
    {
        sum+=(ll)query(1,i);
    }
    cout<<sum<<endl;
    
}