题意：给2个数字序列 a 和 b ，问按从小到达排序后，a中的哪些子串与b的名次匹配。 a 的长度 N≤100,000，b的长度 M≤25,000，数字的大小 K≤25。
解法：【思考】1.X 暴力。枚举 a 中的子串，选出来排序后比对名次。O(n* m log m *m)=O(n*m^2*log m)。
2.X 暴力+树状数组优化。枚举 a 中的子串，选出来后比较前缀名次（P.S.这种转化常出现，比如：【洛谷 p3368】模板-树状数组 2（数据结构） 就是将个体转化为前缀。），看加上自己的之前小于等于和等于该数的个数是否相等。O(n*m log m)。
3.√ kmp+树状数组优化。直接kmp匹配 a串和 b串，next[ ]预处理 b串，再在kmp时看前缀名次来比较。（这个要kmp理解得很好才能在处理树状数组时处理得很好，我现在思绪混乱啊......代码就算了......qwq）
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std; const int N=,M=,K=;
struct node{int x,y,d;}b[M],a[N];
int a[N],b[M],next[M];
int cnt=,s[N];
int ca[K],cb[K]; int lowbit(int x) {return x&-x;}
int change(int x,int d)
{
for (int i=x;i<=n;i+=lowbit(i))
ca[i]+=d;
}
int getcount(int x)
{
int sum=;
for (int i=x;i>=;i-=lowbit(i))
sum+=ca[i];
return sum;
}
int change_2(int x,int d)
{
for (int i=x;i<=m;i+=lowbit(i))
cb[i]+=d;
}
int getcount_2(int x)
{
int sum=;
for (int i=x;i>=;i-=lowbit(i))
sum+=cb[i];
return sum;
}
void init_kmp()
{
memset(cb,,sizeof(cb));
memset(next,,sizeof(next));
int p=,x=,y=;
next[]=;
for (int i=;i<=m;i++)
{
while ((b[i].x!=b[p+].x||b[i].y!=b[p+].y) && p)
{
p=next[p];
}
if (b[i].x==b[p+].x&&b[i].y==b[p+].y)
{
p++;
add_2(b[i].d,);
}
next[i]=p;
}
}
void kmp()
{
int p=;
for (int i=;i<=n;i++)
{
int x=getcount_2(a[i].d-);
while ((a[i].x-(a[i-p].x+a[i-p].y)!=b[p+].x||a[i].y!=b[p+].y) && p) p=next[p];
if (a[i].x==b[p+].x&&a[i].y==b[p+].y) p++;
if (p==m) s[++cnt]=i;
}
}
int main()
{
freopen("a.in","r",stdin);
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
//memset(ca,0,sizeof(ca));
for (int i=;i<=n;i++)
{
scanf("%d",&a[i].d);
/*change(a[i].d,1);
a[i].x=getcount(a[i].d);
a[i].y=a[i].x-getcount(a[i].d-1);*/
}
//memset(cb,0,sizeof(cb));
for (int i=;i<=m;i++)
{
scanf("%d",&b[i].d);
/*change_2(b[i].d,1);
b[i].x=getcount_2(b[i].d);
b[i].y=b[i].x-getcount_2(b[i].d-1);*/
}
init_kmp();
kmp();
printf("%d\n",cnt);
for (int i=;i<=cnt;i++)
printf("%d ",s[i]);
return ;
}
待修改代码...0.0