题解：P10634 BZOJ2372 music

· · 题解

看到这道题 题目加强版 的削弱版了，发一篇O((n+m)\log s)的题解。

题目描述：

给你一个长度为 n 的序列 S，一个长度为 m 的序列 T。序列 S 和 T 的数是 \lbrack 1,x \rbrack 之间的正整数。

定义两个长度相等的串等价：在这两个串中相对顺序不变。

问在 S 中，有多少个子串跟 T 等价，并按顺序输出起始位置。

解法：

首先考虑怎么将等价条件转换为可维护的东西，两个数相对顺序相同意味着小于它们的数的个数相同，等于它们的数的个数相同，大于它们的数的个数也相同。

考虑维护已经匹配的序列中，总数=小于他的数 + 等于他的数 + 大于他的数 ，总数一定，我们只需要维护小于他的数与等于他的数相同就行了，所以我们对值域开一棵树状数组就能维护匹配序列每个数出现的次数，然后就能O(\log n) 判断等价情况，然后套个 kmp 就做完了。

code:

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define FOR(i,a,b) for(int i=(a);i<=(int)b;i++)
#define ROF(i,a,b) for(int i=(b);i>=(int)a;i--)
const int N=1e6+10;
const ll inf=1e18+10;
const ll mod=1e9+7;
const double eps=1e-7;
using Vl=vector<int>;
using PI=array<ll,2>;
int n,k,t[N],v,a[N],b[N],nxt[N],kmp[N],ct[N],ct1[N];//ct存< i的数 ct1存<=i 的数
inline void Clear(){fill(t,t+v+1,0);return ;}
inline void A(int x,int d){for(;x<=v;x+=x&(-x)) t[x]+=d;return ;}
inline int Q(int x){int res=0;for(;x;x-=x&(-x)) res+=t[x];return res;}//三行树状数组
inline bool ck(int x,int y){return Q(x-1)==ct[y]&&Q(x)==ct1[y];}//只需要x,y满足<x数==<y的数，=x的数== =y的数即可判断相等
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
//  ios::sync_with_stdio(0);
//  cin.tie(0);cout.tie(0);
    cin>>n>>k>>v;
    FOR(i,1,n) cin>>a[i];
    FOR(i,1,k) cin>>b[i];
    FOR(i,1,k) A(b[i],1),ct[i]=Q(b[i]-1),ct1[i]=Q(b[i]);
    Clear();//树状数组存的是匹配序列中数的集合，所以后面每次用都要清空
    for(int i=2,j=0;i<=k;i++){
        A(b[i],1);//匹配序列+1
        while(j&&!ck(b[i],j+1)){
            FOR(l,i-j,i-nxt[j]-1) A(b[l],-1);//失配了删掉跳过的数
            j=nxt[j];
        }
        if(ck(b[i],j+1)) j++;
        nxt[i]=j;
    }
    Clear();
    for(int i=1,j=0;i<=n;i++){
        A(a[i],1);
        while(j&&!ck(a[i],j+1)){
            FOR(l,i-j,i-nxt[j]-1) A(a[l],-1);
            j=nxt[j];
        }
        if(ck(a[i],j+1)) j++;
        kmp[i]=j;
    }
    int res=0;
    FOR(i,1,n) res+=(kmp[i]==k);
    cout<<res<<'\n';
    FOR(i,1,n) if(kmp[i]==k) cout<<i-k+1<<'\n';
    return 0;
}

时间复杂度

可能有些人担心这一段：

while(j&&!ck(b[i],j+1)){
            FOR(l,i-j,i-nxt[j]-1) A(b[l],-1);
            j=nxt[j];
        }

多套了一层for循环会不会时间复杂度退化。

里面for循环的意思是删除j \to nxt[j]中跳过的字符，所以树状数组的操作数就等于 j指针的回退量 ，j指针的回退量小于等于增加量O(n) ，所以总操作次数是O(n) 加上树状数组就是 O(n \log s)。所以总时间复杂度就是 O((n+m) \log s)。