完完全全就是segment tree beats的板子题
代码:
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define PLL pair<ll,ll>
const int N=1000010;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
#define int long long
struct Node{
int l,r;
char c;
}e[N];
struct misaka{
int l,r;
ll sum;
ll mi,semi;
ll cnt;
char c;
char tag;
}tr[N<<4];
int n,m;
char s[N];
void push_up(int u){
if(tr[u<<1].mi<tr[u<<1|1].mi){
tr[u].mi=tr[u<<1].mi;
tr[u].cnt=tr[u<<1].cnt;
tr[u].semi=min(tr[u<<1].semi,tr[u<<1|1].mi);
}
else if(tr[u<<1].mi>tr[u<<1|1].mi){
tr[u].mi=tr[u<<1|1].mi;
tr[u].cnt=tr[u<<1|1].cnt;
tr[u].semi=min(tr[u<<1|1].semi,tr[u<<1].mi);
}
else{
tr[u].mi=tr[u<<1].mi;
tr[u].cnt=tr[u<<1].cnt+tr[u<<1|1].cnt;
tr[u].semi=min(tr[u<<1].semi,tr[u<<1|1].semi);
}
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void push_down(int u){
if(tr[u].tag){
if(tr[u<<1].mi<tr[u].tag){
tr[u<<1].sum=tr[u<<1].sum+1ll*(tr[u].tag-tr[u<<1].mi)*tr[u<<1].cnt;
tr[u<<1].mi=tr[u].tag;
tr[u<<1].tag=tr[u].tag;
}
if(tr[u<<1|1].mi<tr[u].tag){
tr[u<<1|1].sum=tr[u<<1|1].sum+1ll*(tr[u].tag-tr[u<<1|1].mi)*tr[u<<1|1].cnt;
tr[u<<1|1].mi=tr[u].tag;
tr[u<<1|1].tag=tr[u].tag;
}
tr[u].tag=0;
}
}
void build(int u,int l,int r){
if(l==r){
tr[u]={l,r,s[l],s[l],INF,1,s[l],0};
return;
}
tr[u]={l,r,0,0,0,0,0,0};
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
push_up(u);
}
void update(int u,int L,int R,char x){
if(tr[u].mi>=x) return;
if(tr[u].l>=L && tr[u].r<=R){
if(x<tr[u].semi){
tr[u].sum=tr[u].sum+1ll*(x-tr[u].mi)*tr[u].cnt;
tr[u].mi=x;
tr[u].tag=x;
return;
}
}
push_down(u);
int mid=(tr[u].l+tr[u].r)>>1;
if(L<=mid) update(u<<1,L,R,x);
if(R>mid) update(u<<1|1,L,R,x);
push_up(u);
}
signed main(){
scanf("%lld %lld",&n,&m);
getchar();
scanf("%s",s+1);
for(int i=1;i<=m;++i){
scanf("%lld %lld %c",&e[i].l,&e[i].r,&e[i].c);
}
//这一步排序其实是多余的
sort(e+1,e+1+m,[&](Node a,Node b){
return a.c<b.c;
});
build(1,1,n);
for(int i=1;i<=m;++i) update(1,e[i].l,e[i].r,e[i].c);
printf("%lld\n",tr[1].sum);
return 0;
}