P6080题解

· · 题解

前言

第一眼看到题目，觉得是 kmp+平衡树，仔细一做，结果写出了 kmp+线段树（前置知识）

解法

读题我们知道，这是一道 kmp，比较是用的每个数的大小关系

上来我直接算出每个数加入时的排名，用这个跑了一遍 kmp（WA 声一片~）

仔细读题，发现 S 只有25，所以就有很多重复的号码，出现正确性问题

那么，我们可以多记录一个值，与自己相同的数有多少个，与排名一起判断，就能保证正确性

我们可以用线段树维护这个 kmp，一个数只会进出线段树各一次，所以时间复杂度为 \Theta(\log{n}+\log{k}) ，完美通过， 73ms ，最优解第四

CODE

代码如下

#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e5+10;
int n,k,s,cnt,hed,res;
int nex[MAX],rnk[MAX],sum[MAX],a[MAX],b[MAX],ans[MAX];
int ls[110];
inline int read() {
    int x = 0;
    char ch = getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x;
}
//线段树
void build(int l,int r,int lr){
    ls[lr]=0;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(l,mid,lr<<1),build(mid+1,r,lr<<1|1);
}
void add(int l,int r,int x,int v,int lr){
    ls[lr]+=v;
    if(l==r) return;
    int mid = (l+r)>>1;
    if(x<=mid) add(l,mid,x,v,lr<<1);
    else add(mid+1,r,x,v,lr<<1|1);
}
int query(int l,int r,int L,int R,int lr){
    if(R<L) return 0;
    if(l>=L and r<=R) return ls[lr];
    int mid=(l+r)>>1,res=0;
    if(mid>=L) res=query(l,mid,L,R,lr<<1);
    if(mid<R) res+=query(mid+1,r,L,R,lr<<1|1);
    return res; 
}
//处理 next 数组，初始化
void init(){
    for(int i = 1;i<=k;++i) add(1,s,b[i],1,1),rnk[i]=query(1,s,1,b[i]-1,1),sum[i]=query(1,s,b[i],b[i],1);
    build(1,s,1);
    int p=0;
    for(int i = 2;i<=k;++i){
        add(1,s,b[i],1,1);
        int l=query(1,s,1,b[i]-1,1),r=query(1,s,b[i],b[i],1);
        while(p and (l!=rnk[p+1] or r!=sum[p+1])){
            for(int j = i-p;j<i-nex[p];j++) {
                add(1,s,b[j],-1,1);
                if(b[j]==b[i]) --r;
                if(b[j]<b[i]) --l;
            }
            p=nex[p];
        }
        if(l==rnk[p+1] and r==sum[p+1]) p++;
        nex[i] = p;
    }
    build(1,s,1);
}
signed main() {
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    n = read(),k = read(),s = read();
    for(int i = 1;i<=n;++i) a[i]=read();
    for(int i = 1;i<=k;++i) b[i]=read();
    init();
    int p = 0;
    for(int i = 1;i<=n;++i){
        add(1,s,a[i],1,1);
        int l=query(1,s,1,a[i]-1,1),r=query(1,s,a[i],a[i],1);//提前记录，以免时间爆炸
        while(p and (l!=rnk[p+1] or r!=sum[p+1])) {
            for(int j = i-p;j<i-nex[p];++j) {
                add(1,s,a[j],-1,1);
                if(a[j]==a[i]) r--;//更新当前的排名与相同字符数
                if(a[j]<a[i]) l--;
            }
            p=nex[p];
        }
        if(l==rnk[p+1] and r==sum[p+1])++p;
        if(p==k) ans[++res]=i-k+1;
    }
    printf("%d\n",res);
    for(int i = 1;i<=res;++i) printf("%d\n",ans[i]);
    return 0;
}