BZOJ 1461 && BZOJ 1729
KMP+BIT
一看就是字符串匹配但是不同的是要按照每个字符的排名情况。
首先对于数字x的排名,那么要判断x前小于x的数的个数,和x前小于等于x的数的个数,这两个都相等才相等。因为会有数字会有重复的.
然后可以先预处理出字串的每个数字的排名,这样就不需要两个BIT了。最后按照KMP的思路做就可以了.
#include <cstdio>
#include <cstring>
const int MaxN=;
const int MaxS=;
int a[MaxN],b[MaxN],Rk1[MaxN],Rk2[MaxN],Ans[MaxN],tot,n,k,s,P[MaxN];
int c[MaxS];
inline int Lowbit(int x) {return x&-x;}
inline void Add(int x,int d)
{for (int i=x;i<=s;i+=Lowbit(i)) c[i]+=d;}
inline int Query(int x)
{
int Ret=;
for (int i=x;i;i-=Lowbit(i)) Ret+=c[i];
return Ret;
}
int main()
{
scanf("%d%d%d",&n,&k,&s);
for (int i=;i<=n;i++) scanf("%d",&a[i]);
for (int i=;i<=k;i++)
{
scanf("%d",&b[i]); Add(b[i],);
Rk1[i]=Query(b[i]),Rk2[i]=Query(b[i]-);
}
memset(c,,sizeof(c)); int j=;
for (int i=;i<=k;i++)
{
Add(b[i],);
while (j && ((Query(b[i])!=Rk1[j+]) || (Query(b[i]-)!=Rk2[j+])))
{
for (int l=i-j;l<i-P[j];l++) Add(b[l],-);
j=P[j];
}
if ((Query(b[i])==Rk1[j+]) && (Query(b[i]-)==Rk2[j+])) j++;
P[i]=j;
}
memset(c,,sizeof(c)); j=;
for (int i=;i<=n;i++)
{
Add(a[i],);
while (j && (Query(a[i])!=Rk1[j+] || Query(a[i]-)!=Rk2[j+]))
{
for (int l=i-j;l<i-P[j];l++) Add(a[l],-);
j=P[j];
}
if (Query(a[i])==Rk1[j+] && Query(a[i]-)==Rk2[j+]) j++;
if (j==k)
{
Ans[++tot]=i-j+;
for (int l=i-j+;l<=i-P[j];l++) Add(a[l],-);
j=P[j];
}
}
printf("%d\n",tot);
for (int i=;i<=tot;i++) printf("%d\n",Ans[i]);
return ; }
双倍经验