题解：P12667 [KOI 2023 Round 2] 傻瓜锁

· · 题解

upd：修改了错误的例子。

分析

本来看到这题第一眼想到了用数据结构维护 dp 值的，然后就想不到后续了，就去看题解，结果题解也看不懂。

后来我就想，我要不干脆直接把 dp 扔掉，只保留数据结构呢？

我们发现这个字符串改完之后是不降的，其实意味着我们可以弄出 26 个区间 [l_1,r_1),[l_2,r_2),\cdots,[l_{26},r_{26})，使得 [l_1,r_1) 之间全部是 a、[l_2,r_2) 之间全部是 b，以此类推。特别地，如果 l_i=r_i，意味着第 i 个小写字母在字符串中不存在。也就是说，如果我们能在开始和每次修改后设法找到这 26 个区间，那么这道题就可以做完。

我们提一下另外一部分思路。首先这个串可以先被变成全都是 a 的串，这个串一定是不降的，但不一定是最少操作次数的，因为有很多冗余操作，这时我们就要反悔。例如样例 1 中的串 ababba，我如果把它全变成 a 要花费 3 次操作，这时如果我把那些 b 反悔了，连同中间夹着的 a 一起变为 b，那么序列是 abbbbb，仅需 2 次操作。这样反悔为啥减少了操作次数？因为每反悔一个比 a 大的字符变为 b，就减少了一次冗余操作，但每把一个小于等于 a 的字符反悔为一个 b，就增加了一次操作。不过在样例中，减少的多于增加的，所以总操作减少了。我们又会发现，当我们进行反悔操作时，由于整个序列必须是不降，那么我们一定会反悔串的一个后缀，此时那些每被反悔掉的字符就变成了上一段提到的区间。举个例子：abadc，在一开始变成 aaaaa 后，发现后 4 位中大于 a 的字符数比小于等于 a 的多，所以反悔一次，字符串变为 abbbb，可得出 l_1=1,r_1=2，因为这个区间不会再改变，区间外的字符也不会变成它了；继续操作，可以把后 2 位再反悔了，字符串变为 abbcc；再然后发现再反悔没有意义了，所以这个串会变成 abbcc（这次是操作数最少的了）。

那你可能会问，我只知道最终序列变成了啥，我怎么知道要几次操作啊？那我们可以先从如何决定反悔操作说起。把上一段所说的反悔操作描述一下，就是我们找到当前未判断是否需要反悔的那段后缀，找到后缀中的一个位置，且那个位置往后的字符中，大于等于要反悔为的字符数量减小于的尽可能大，就在那个位置反悔后缀。如果有多个这种位置，取更靠前的一定不劣；如果那个位置处反悔都不优，那就结束反悔流程。此时问题转化为单点修改，区间查询最大值以及其位置，这个不难。这样一来，我们其实也知道了一个区间反悔的时候减少的操作数减去增加的操作数，只要统计出一开始把字符串变为全 a 的操作数再减去后面每次反悔的该值就可以得出最终所需的操作数。

由于我们需要对每个字符都维护后缀大于等于它的减小于它的有多少，所以要开 26 棵线段树，空间复杂度 O(|\Sigma||S|)，时间复杂度 O(|\Sigma||S|\log |S|)，可以通过。

AC Code


#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int tr[N<<2][27],lz[N<<2][27],pos[N<<2][27],n,cnt[27],a[N][27];
int sum;
string str;
void pushup(int type,int p)
{
    tr[p][type]=max(tr[p<<1][type],tr[p<<1|1][type]);
    if(tr[p<<1][type]>=tr[p<<1|1][type]) pos[p][type]=pos[p<<1][type];
    else pos[p][type]=pos[p<<1|1][type];
}
void build(int type,int s=1,int t=n,int p=1)
{
    if(s==t)
    {
        tr[p][type]=a[s][type];
        pos[p][type]=s;
        return;
    }
    int m=s+t>>1;
    build(type,s,m,p<<1);build(type,m+1,t,p<<1|1);
    pushup(type,p);
}
void upd(int type,int l,int r,int c,int s=1,int t=n,int p=1)
{
    if(l<=s&&t<=r)
    {
        tr[p][type]+=c;
        lz[p][type]+=c;
        return;
    }
    int m=s+t>>1;
    if(lz[p][type])
    {
        lz[p<<1][type]+=lz[p][type];
        lz[p<<1|1][type]+=lz[p][type];
        tr[p<<1][type]+=lz[p][type];
        tr[p<<1|1][type]+=lz[p][type];
        lz[p][type]=0;
    }
    if(l<=m) upd(type,l,r,c,s,m,p<<1);
    if(r>m) upd(type,l,r,c,m+1,t,p<<1|1);
    pushup(type,p);
}
int ps;
int qmax(int type,int l,int r,int s=1,int t=n,int p=1)
{
    if(l<=s&&t<=r)
    {
        ps=pos[p][type];
        return tr[p][type];
    }
    int m=s+t>>1;
    int ans=0;
    if(lz[p][type])
    {
        lz[p<<1][type]+=lz[p][type];
        lz[p<<1|1][type]+=lz[p][type];
        tr[p<<1][type]+=lz[p][type];
        tr[p<<1|1][type]+=lz[p][type];
        lz[p][type]=0;
    }
    if(r>m) ans=qmax(type,l,r,m+1,t,p<<1|1);
    if(l<=m) ans=max(ans,qmax(type,l,r,s,m,p<<1));
    return ans;
}
inline void query()
{
    int ans=sum-n;
    int pt=1;
    for(int i=2;i<=26;i++)
    {
        int mx=qmax(i,pt,n);
        if(mx<=0) break;
        ans-=mx;
        pt=ps;
    }
    cout<<ans<<'\n'; 
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>str;
    n=str.size();
    str=' '+str;
    for(int i=n;i;i--)
    {
        cnt[str[i]-'a'+1]++;
        sum+=str[i]-'a'+1;
        int nsum=0;
        for(int j=26;j;j--)
        {
            nsum+=cnt[j];
            a[i][j]=nsum-(n-i+1-nsum);
        }
    }
    for(int i=1;i<=26;i++) build(i);
    query();
    int q;
    cin>>q;
    while(q--)
    {
        int k;
        char x;
        cin>>k>>x;
        sum-=str[k]-'a'+1;
        for(int i=1;i<=str[k]-'a'+1;i++) upd(i,1,k,-1);
        for(int i=str[k]-'a'+2;i<=26;i++) upd(i,1,k,1);
        str[k]=x;
        sum+=x-'a'+1;
        for(int i=1;i<=x-'a'+1;i++) upd(i,1,k,1);
        for(int i=x-'a'+2;i<=26;i++) upd(i,1,k,-1);
        query();
    }
}