my
[[discretization]] [[SA]] [[RMQ]] [[Binary Search]] [[Sweep Line]] [[BIT]] [[difference]]
OHHHHH OHHHH OHHHHHHHHH I made it!!!!
![[Pasted image 20220912204126.png]]
Process
先把原序列变为差分数组
%%Change the original sequence to a difference array(差分数组).%%
能够匹配的区间与在差分数组中查询的区间正好互为相反数
%%And the interval which is able to be matched is the same as the reversed(negative) inquiring interval in difference array.%%
我们要找出所有能够匹配的区间，所以可以使用后缀数组
%%We should find out all the interval able to be matched, so we can use suffix array.%%
为了得到查询区间的起始位置，我们可以将取了相反数的序列放到原序列的后面，以inf分隔
%%To get the start positions of the inquiring interval, we can put the reversed sequence to the back of positive-going sequence, separated by inf.%%
现在，我可以通过二分搜索(一次左，一次右)得到满足第二个和第三个条件的所有区间，然后减去在辅助序列（加在后面的序列）里的区间
%%Now, I can get all the intervals which meet the second and third conditions via binary search(once left, once right).%% ^uwb2pq
然而，我们还没有完全解决这个问题(时间复杂度不正确)，不能真的遍历一遍
%%However, we have not yet definitely solved this problem (see the range of data).%%
怎么解决这个有趣的状况？
离线
%%How to deal with the intersect condition? offline%%
考虑扫描线（因为有sa<l or sa>r的限制，不能前缀和，成了二维数点）
%%Considering sweep line. %%
可以用BIT、线段树，或者其他支持单点修改区间求和的数据结构
%%We could solve it using BIT or segment tree or other structure that support queries of sum on an interval and increment(单点修改) of an element.
%%
要注意上下左右边界，要减去的是什么，要加上的是什么
%%Pay attention to the gap near end pos, start pos, the add item and the subtract item.
%%
#include<bits/stdc++.h>
using namespace std;
const int N=400005;
int t,tot,n,nn,Q,m,r[N],d[N];
int t1[N],t2[N],sa[N],w[N],h[N],rk[N];
void SA(){
int *as=t1,*psa=t2,p,i,j,k;
for(i=0;i<=m;i++)w[i]=0;
for(i=1;i<=n;i++)w[r[i]]++;
for(i=1;i<=m;i++)w[i]+=w[i-1];
for(i=n;i;i--)sa[w[as[i]=r[i]]--]=i;
for(j=1;;j<<=1){
for(p=0,i=n+1-j;i<=n;i++)psa[++p]=i;
for(i=1;i<=n;i++)if(sa[i]>j)psa[++p]=sa[i]-j;
for(i=0;i<=m;i++)w[i]=0;
for(i=1;i<=n;i++)w[as[psa[i]]]++;
for(i=1;i<=m;i++)w[i]+=w[i-1];
for(i=n;i;i--)sa[w[as[psa[i]]]--]=psa[i];
for(m=psa[sa[1]]=1,i=2;i<=n;i++)
psa[sa[i]]=(as[sa[i]]==as[sa[i-1]]&&as[sa[i]+j]==as[sa[i-1]+j]?m:++m);
if(m==n)break;swap(as,psa);
}
for(i=1;i<=n;i++)rk[i]=psa[i];
for(i=1,k=0;i<=n;i++){
j=sa[rk[i]-1];
while(r[i+k]==r[j+k])k++;
h[rk[i]]=k;if(k>0)k--;
}
}
int f[N<<1][25];
void RMQ(){
int i,j;
for(i=1;i<=n;i++)f[i][0]=h[i];
for(j=1;j<=21;j++)
for(i=1;i+(1<<j)-1<=n;i++)
f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
int lg[N];
int lcp(int x,int y){
if(x>y)swap(x,y);
int g=lg[y-x+1];
return min(f[x][g],f[y-(1<<g)+1][g]);
}
////another way to implement the LCP
//bool check1(int p){
// ret=1000006;
// for(int j=21;j>=0;j--){
// if(p+(1<<j)-1<=_){
// ret=min(f[p][j],ret);
// p+=1<<j;
// }
// }
// if(ret<len)return 0;
// else return 1;
//}
//bool check2(int p){
// ret=1000006;
// for(int j=21;j>=0;j--){
// if(p-(1<<j)+1>_){
// ret=min(f[p-(1<<j)+1][j],ret);
// p-=1<<j;
// }
// }
// if(ret<len)return 1;
// else return 0;
//}
/*45124514*/
int len,x,y,_;
struct NODE{
int id,x,y,p,o;
}q[N];
void erf(){
int l=2,r=_,mid;
while(l<=r){
mid=l+r>>1;
if(lcp(mid,_)>=len)r=mid-1;
else l=mid+1;
}
q[tot].o=-1;
q[tot].p=r-1;
l=_+1,r=n;
while(l<=r){
mid=l+r>>1;
if(lcp(mid,_+1)<len)r=mid-1;
else l=mid+1;
}
q[tot+1].o=1;
q[tot+1].p=r;
}
int bi[N];
void up(int p){
for(;p<=nn;p+=p&-p)bi[p]++;
}
int ret;
int down(int p){
for(ret=0;p;p-=p&-p)ret+=bi[p];
return ret;
}
int ans[N],cnt;
int main(){
int i;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&r[i]);
for(i=1;i<n;i++){
d[i]=r[i+1]-r[i],
d[i+n]=-d[i];
} d[n]=1e9;
nn=n;n=n*2-1;
for(i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
for(i=1;i<=n;i++)r[i]=d[i];
sort(d+1,d+1+n);
m=unique(d+1,d+1+n)-d;
for(i=1;i<=n;i++)r[i]=lower_bound(d+1,d+m,r[i])-d;m=n;
SA();RMQ();
scanf("%d",&Q);
for(i=1;i<=Q;i++){
scanf("%d%d",&x,&y);
if(x==y){
ans[i]=nn-1;
continue;
}
len=y-x;_=rk[x+nn];erf();
q[tot].x=q[tot+1].x=max(x-1-len,0);
q[tot].y=q[tot+1].y=y;
q[tot].id=q[tot+1].id=i;
tot+=2;
}
sort(q,q+tot,[](NODE a,NODE b){
return a.p<b.p;
});
for(i=0;i<=n;i++){
if(sa[i]<=nn&&sa[i]>=1)up(sa[i]),cnt++;
for(;q[t].p==i&&t<tot;t++)
ans[q[t].id]+=q[t].o*(cnt-down(q[t].y)+down(q[t].x));
if(t>=tot)break;
}
for(i=1;i<=Q;i++)printf("%d\n",ans[i]);
}