题意就是差分后求形如ABA的串的个数，B的长度为M
这是2011国家集训队互测的试题，是道好题，我直接给出出题人的题解吧：
对于这种在线性序列上的组合计数问题，我们很容易想到一个工具：分治！分治算法在形如快速排序等地方能顺利优化算法，我们尝试将其运用至本题中。
不妨设过程F(Left,Right)可以统计在区间[Left,Right]中满足条件的子序列的个数。
设Mid为区间[Left,Right]的中点由于分治执行，我们不需要统计那些属于[Left,Mid],[Mid+1,Right]中的子序列，剩下的我们分两种情况讨论。
1、 点Mid∈Q。这种情况由于|Q|非常小，我们可以直接枚举Q的位置，然后我们可以穷举A部分长度，然后后缀数组+RMQ解决这个问题
此时算法多了一个系数M，不过整体仍然可以在O(NMLogN)的复杂度内完成。
2、 点Mid∉Q，这种情况就比较麻烦了，可以表示成如下示意图：
由于Mid的存在，P2被分割成了3份，由于P1=P2，我们把P1也分割成3份，经过仔细观察，我们发现只需要枚举红线的位置即可解决此部分的统计问题。黄色部分的最大匹配值可以通过将整个Mid左面的部分倒置后求LCP可得。而Mid以及绿色部分的匹配值可以直接通过后缀数组+RMQ求的。知道了绿色与黄色部分的最大值后，那么Q的位置个数也可以相应得出，问题得到解决，此部分复杂度为O(NLogN)。
方法三总复杂度为O(NMLogN)，为一个非常优秀的算法。
const eps=1e-8;
var s,h,sa,rank:array[..,..] of longint;
sum,a,b,x,y:array[..] of longint;
f:array[..,..,..] of longint;
d:array[..] of longint;
t,mx,ans,i,n,m:longint; procedure swap(var a,b:longint);
var c:longint;
begin
c:=a;
a:=b;
b:=c;
end; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure suffix(k:longint);
var i,j,m,p:longint;
begin
fillchar(sum,sizeof(sum),);
for i:= to n do
inc(sum[s[i,k]]);
for i:= to mx do
inc(sum[i],sum[i-]);
for i:=n downto do
begin
sa[sum[s[i,k]],k]:=i;
dec(sum[s[i,k]]);
end;
p:=;
rank[sa[,k],k]:=;
for i:= to n do
begin
if s[sa[i,k],k]<>s[sa[i-,k],k] then inc(p);
rank[sa[i,k],k]:=p;
end;
m:=p;
j:=;
while m<n do
begin
for i:= to n do
begin
y[i]:=rank[i,k];
sum[i]:=;
end;
p:=;
for i:=n-j+ to n do
begin
inc(p);
x[p]:=i;
end;
for i:= to n do
if sa[i,k]>j then
begin
inc(p);
x[p]:=sa[i,k]-j;
end; for i:= to n do
begin
a[i]:=y[x[i]];
inc(sum[a[i]]);
end;
for i:= to m do
inc(sum[i],sum[i-]);
for i:=n downto do
begin
sa[sum[a[i]],k]:=x[i];
dec(sum[a[i]]);
end;
p:=;
rank[sa[,k],k]:=;
for i:= to n do
begin
if (y[sa[i,k]]<>y[sa[i-,k]]) or (y[sa[i,k]+j]<>y[sa[i-,k]+j]) then inc(p);
rank[sa[i,k],k]:=p;
end;
m:=p;
j:=j shl ;
end;
h[,k]:=;
p:=;
for i:= to n do
begin
if rank[i,k]= then continue;
j:=sa[rank[i,k]-,k];
while (i+p<=n) and (j+p<=n) and (s[i+p,k]=s[j+p,k]) do inc(p);
h[rank[i,k],k]:=p;
if p> then dec(p);
end;
for i:= to n do
f[i,,k]:=h[i,k];
for j:= to t do
for i:= to n do
if i+d[j]-<=n then
f[i,j,k]:=min(f[i,j-,k],f[i+d[j-],j-,k])
else break;
end; function ask(l,r,k:longint):longint;
var p:longint;
begin
if l>r then swap(l,r);
inc(l);
p:=trunc(ln(r-l+)/ln()+eps);
exit(min(f[l,p,k],f[r-d[p]+,p,k]));
end; procedure work(l,r:longint);
var mid,i,j,x,y:longint;
begin
if r-l+<m+ then exit;
mid:=(l+r) shr ;
for i:=mid-m+ to mid do
for j:=i- downto l do
begin
if r-(i+m)+<i-j then break;
if ask(rank[j,],rank[i+m,],)>=i-j then inc(ans);
end; for i:=l to mid-m- do
begin
x:=min(ask(rank[i,],rank[mid,],),mid-i-m);
if (x<) then continue;
y:=ask(rank[n+-i,],rank[n+-mid,],);
y:=min(y-,min(i-l,mid-i-m-));
if y<mid-i-m-x then continue;
ans:=ans+min(x,y-(mid-i-m-x)+);
end;
for i:=mid+m+ to r do
begin
y:=min(i-mid-m,ask(rank[n+-i,],rank[n+-mid,],));
if y< then continue;
x:=ask(rank[i+,],rank[mid+,],);
x:=min(x,min(r-i,i-mid-m-));
if x<i-mid-m-y then continue;
ans:=ans+min(y,x-(i-mid-m-y)+);
end;
work(l,mid-);
work(mid+,r);
end; procedure sort(l,r:longint);
var i,j,x:longint;
begin
i:=l;
j:=r;
x:=a[(l+r) shr ];
repeat
while a[i]<x do inc(i);
while x<a[j] do dec(j);
if not(i>j) then
begin
swap(a[i],a[j]);
swap(b[i],b[j]);
inc(i);
dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end; begin
readln(n,m);
for i:= to n do
read(a[i]);
dec(n);
for i:= to n do
s[i,]:=a[i+]-a[i]; for i:= to n do
begin
a[i]:=s[i,];
b[i]:=i;
end;
sort(,n);
mx:=;
s[b[],]:=;
for i:= to n do
begin
if a[i]<>a[i-] then inc(mx);
s[b[i],]:=mx;
end;
for i:= to n do
s[i,]:=s[n+-i,];
t:=trunc(ln(n)/ln()+eps);
d[]:=;
for i:= to t do
d[i]:=d[i-]*;
suffix();
suffix();
work(,n);
writeln(ans);
end.