先说思路：
因为我们是比对较短的\(B\)与较长的\(A\)的子串，所以我们求不变的\(B\)的\(next\)
对于这道题我们可以使用树状数组查询前缀和维护数的排名。
对于相同的数我们查询的排名是有误的，因此不仅要比对小于等于该数的前缀和，也要比对小于该数的前缀和。
如:对于\(A=2\) \(2\),\(B=1\) \(2\)，来说，\(A\)的第二个\(2\)排名应为\(1\)，但是前缀和是\(2\)。
对于代码有一求助问题。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e6+50;
int n,k,s,next_[maxn];
int A[maxn],B[maxn],c[maxn];
int ranq[maxn],ress[maxn];
int ans,anss[maxn];
int lowbit(int x){
return x&(-x);
}
void update(int x,int y){
while(x<=s){
c[x]+=y;
x+=lowbit(x);
}
}
int query(int x){
int ans2=0;
while(x){
ans2+=c[x];
x-=lowbit(x);
}
return ans2;
}
inline void input(){
scanf("%d %d %d",&n,&k,&s);
for(int i=1;i<=n;++i){
scanf("%d",&A[i]);
}
for(int i=1;i<=k;++i){
scanf("%d",&B[i]);
update(B[i],1);
ranq[i]=query(B[i]);
ress[i]=query(B[i]-1);
//cout<<"%%%"<<i<<' '<<ranq[i]<<' '<<ress[i]<<endl;
}
}
inline void Next(){
for(int i=2,j=0;i<=k;++i){
while(j && (query(B[i])!=ranq[j+1] || query(B[i]-1)!=ress[j+1])){
j=next_[j];
}
++j;
next_[i]=j;
}
}
inline void match(){
for(int i=1,j=0;i<=n;++i){
update(A[i],1);
while(j &&(query(A[i])!=ranq[j+1] || query(A[i]-1)!=ress[j+1])){
//cout<<i<<' '<<j+1<<' '<<A[i]<<' '<<query(A[i])<<' '<<ranq[j+1]<<' '<<query(A[i]-1)<<' '<<ress[j+1]<<endl;
for(int q=i-j;q<i-next_[j];++q){
update(A[q],-1);
//比对相同区间把前面的删去
}
//cout<<"$$$"<<j<<' '<<next_[j]<<endl;
j=next_[j];
}
//cout<<"###"<<i<<' '<<j<<endl;
j++;
if(j==k) anss[++ans]=i-j+1;
}
}
int main(){
input();
Next();
memset(c,0,sizeof(c));
match();
printf("%d\n",ans);
for(int i=1;i<=ans;++i){
printf("%d\n",anss[i]);
}
return 0;
}
我们可以看到\(next\)我写的是：
inline void Next(){
for(int i=2,j=0;i<=k;++i){
while(j && (query(B[i])!=ranq[j+1] || query(B[i]-1)!=ress[j+1])){
j=next_[j];
}
++j;
next_[i]=j;
}
}
前面也没有清空树状数组。
但是网上的很多题解都写的是：
void get_next(){
memset(BIT, 0, sizeof(BIT));
next[1] = 0;
int i = 2, j = 0, k;
for (; i <= m; ++i){
add(b[i], 1);
while (j && (query(b[i] - 1) != les[j + 1] || query(b[i]) != equ[j + 1])){
for (k = i - j; k < i - next[j]; ++k)
add(b[k], -1);
j = next[j];
}
next[i] = ++j;
}
}
我与mp讨论后认为，不清空才是正确的，因为求\(next\)的过程中我们没有将第一个数字放入树状数组，对前缀和一定是有影响的，但是事实上，两种写法都AC了这道题目。
求解答。
标签：前缀,BZOJ1461,int,题解,void,求助,next,maxn From： https://www.cnblogs.com/sonnety-v0cali0d-kksk/p/17570321.html