题解：P9522 [JOISC 2022] 错误拼写

· · 题解

https://www.luogu.com.cn/problem/P9522

如果 s_{A+1}\ne s_A，那么它们的大小关系就决定了 T_A 和 T_B 的大小关系。 如果 s_{A+1}=s_A，我们继续比较下一位。T_A 的第 A+1 位是 s_{A+2}，T_B 的第 A+1 位是 s_{A+1}。因为 s_{A+1}=s_A，所以我们实际在比较 s_{A+2} 和 s_A，我们以此类推继续比较下一位，也就是说我们实际比较的是 s_{A+1\sim B}<s_{A\sim B-1}。

设 f_{i,j} 为前 i 个位置，且 s_i=j 的方案数，因为从前往后转移会转移重复，我们在给状态再加一维 0/1 表示是否 s_{i-1}\ne s_i。

对于 f_{i,j,0} 显然从 f_{i-1,j,0}+f_{i-1,j,1} 转移过来，接着我们枚举 l,k 两个端点，f_{i,j,1} 从 l,k 转移过来。

这样我们就是 O((26n)^2)，考虑如何优化。

首先我们可以消掉 26 的常数，我们令 sum_{i,j}=\sum^{26}_{j=1}f_{i,j,1}，但这还是远远不够。

我们接着对每个起点 s 预处理出该起点出发，类型为 0/1 的边的最大终点 mx_{s}，那么我们把每个起点 s 的贡献视作对区间 [s+1, mx_{s}]，用大根堆维护当前仍然有效的起点。

因为我们知道了起点和终点，这样便于我们把对 l 的前缀和保存下来，对于每次转移，我们只需要 O(1)，这样我们就通过了此题。

#include<bits/stdc++.h>
#define int long long
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
using namespace std;
const int N=500000+10,mod=1e9+7;
int n,m,tot;
int f[N][26][2],ans;
int s[N][26];
int mx0[N],mx1[N];
int l0[N],l1[N];
int S[26][N];
vector<int> V0[N],V1[N];
priority_queue<pair<int,int>> q0,q1;
signed main(){
    // freopen("misspelling.in","r",stdin);
    // freopen("misspelling.out","w",stdout);
    cin>>n>>m;
    rep(i,1,m){
        int x,y; cin>>x>>y;
        if(x==y) continue;
        ++tot;
        if(x>y) mx0[y]=max(mx0[y],x);
        else mx1[x]=max(mx1[x],y);
    }
    rep(i,1,n-1){
        if(mx0[i]>0) V0[i+1].push_back(i);
        if(mx1[i]>0) V1[i+1].push_back(i);
    }
    rep(i,1,n){
        for(auto st:V0[i]) q0.push({st,mx0[st]});
        for(;!q0.empty()&&q0.top().second<i;) q0.pop();
        l0[i]=q0.empty()?0:q0.top().first;
        for(auto st:V1[i]) q1.push({st,mx1[st]});
        for(;!q1.empty()&&q1.top().second<i;) q1.pop();
        l1[i]=q1.empty()?0:q1.top().first;
    }
    rep(i,0,25) f[1][i][1]=1;
    rep(j,0,25) s[1][j]=j+1;
    rep(t,0,25) S[t][1]=s[1][t];
    rep(i,2,n){
        rep(j,0,25){
            f[i][j][0]=(f[i-1][j][0]+f[i-1][j][1])%mod;
            int R=i-1;
            if(j<25&&l0[i]<=R){
                f[i][j][1]=(f[i][j][1]+S[25][R]-S[j][R]-(S[25][l0[i]]-S[j][l0[i]])+mod)%mod;
            }
            if(j>0&&l1[i]<=R){
                f[i][j][1]=(f[i][j][1]+S[j-1][R]-S[j-1][l1[i]]+mod)%mod;
            }
        }
        s[i][0]=f[i][0][1];
        rep(j,1,25) s[i][j]=(s[i][j-1]+f[i][j][1])%mod;
        rep(t,0,25) S[t][i]=(S[t][i-1]+s[i][t])%mod;
    }
    rep(i,0,25){
        ans=(ans+f[n][i][0]+f[n][i][1])%mod;
    }
    cout<<ans;
    return 0;
}