cf232D(后缀数组+主席树+ST表+二分)

Posted on   |   In ,

题意

给定长度为$n$的整数序列

$q​$次查询 区间$[l,r]​$能’’匹配’’多少长度与其一致且不相交的区间 匹配的定义是for all $i​$ $(0 ≤ i≤ r1 - l1)​$ the following condition holds: $h1 + i + hl2 + i = hl1 + hl2​$

题解:

从这个匹配入手

对于两个串 $[l,r]$ $[lx,rx]$

for all $i$ $(1 ≤ i≤ r - l)$ $h_{i+l}-h_{i+l-1}=h_{lx+i-1}-h_{i+lx}$

所以把这个串复制一遍加在后面 注意用一个从未出现的数隔开

然后前面一段用$h_i-h_{i+1}$替代

后面一部分用$h_{i}-h_{i-1}$ 替代

然后链接以后跑后缀数组

对于每个查询 找到$lcp>=r-l$的最大范围[l,r] 然后用主席树维护答案即可

复杂度$O(nlogn+qlogn)$

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const double eps=1e-8;
const int mod=1e9+9;
const int inf=1e9+9;
#define ll long long
using namespace std;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}


int n,a[MAXN],sz;
int str[MAXN],len;
vector<int>vec;
int t1[MAXN],t2[MAXN],txt[MAXN],rank1[MAXN],rank2[MAXN],td[MAXN],sa[MAXN];
bool cmp(int f[],int t,int w,int k){return f[t]==f[w]&&f[t+k]==f[w+k];}
void Sa(){
    int m=++sz;
    int *td=t1;int *rank1=t2;
    for(int i=0;i<m;i++)txt[i]=0;
    for(int i=0;i<len;i++)txt[str[i]]++,rank1[i]=str[i];
    for(int i=1;i<m;i++)txt[i]+=txt[i-1];
    for(int i=len-1;i>=0;i--)sa[--txt[str[i]]]=i;
    for(int k=1;k<=len;k<<=1){
	int p=0;
	for(int i=len-k;i<len;i++)td[p++]=i;
	for(int i=0;i<len;i++)if(sa[i]>=k)td[p++]=sa[i]-k;
	for(int i=0;i<m;i++)txt[i]=0;
	for(int i=0;i<len;i++)txt[rank1[i]]++;
	for(int i=1;i<m;i++)txt[i]+=txt[i-1];
	for(int i=len-1;i>=0;i--)sa[--txt[rank1[td[i]]]]=td[i];
	swap(rank1,td);rank1[sa[0]]=0;
	p=1;
	for(int i=1;i<len;i++)rank1[sa[i]]=cmp(td,sa[i],sa[i-1],k)?p-1:p++;
	if(p>=len)break;
	m=p;
    }
    for(int i=0;i<len;i++)rank2[sa[i]]=i;
}

int h[MAXN],H[MAXN];
void hh(){
    for(int i=0;i<len;i++){
	if(!rank2[i])continue;
	int t=sa[rank2[i]-1];int w=i;int k;
	if(i==0||H[i-1]<=1)k=0;else k=H[i-1]-1,t+=k,w+=k;
	while(t<len&&w<len){
	    if(str[w]==str[t])k++;
	    else break;
	    w++;t++;
	}
	H[i]=k;h[rank2[i]]=k;
    }
}
int dp[MAXN][21],ma[MAXN];
void St(){
    for(int i=2;i<=len;i++)ma[i]=ma[i/2]+1;
    for(int i=1;i<len;i++)dp[i][0]=h[i];
    for(int j=1;j<=20;j++){
	for(int i=1;i+(1<<j)<=len;i++){
	    dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
	}
    }
}
int rmq(int l,int r){
    l++;
    if(l>r)return 0;
    int k=ma[r-l+1];
    return min(dp[l][k],dp[r-(1<<k)+1][k]);
}
pii solve(int x,int t){
    int l=x+1;int r=len-1;pii ans;ans.second=x;
    while(l<=r){
	int mid=(l+r)>>1;
	if(rmq(x,mid)>=t)ans.second=mid,l=mid+1;
	else r=mid-1;
    }
    l=1;r=x-1;ans.first=x+1;
    while(l<=r){
	int mid=(l+r)>>1;
	if(rmq(mid,x)>=t)ans.first=mid,r=mid-1;
	else l=mid+1;
    }
    return ans;
}
int rt[MAXN];
int cnt;
typedef struct node{
    int l,r,sum;
}node;
node d[MAXN*21];
void update(int &x,int y,int l,int r,int t){
    x=++cnt;d[x]=d[y];d[x].sum++;
    if(l==r)return ;
    int mid=(l+r)>>1;
    if(t<=mid)update(d[x].l,d[y].l,l,mid,t);
    else update(d[x].r,d[y].r,mid+1,r,t);
}
int ans1;
void query(int x,int y,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){ans1+=d[y].sum-d[x].sum;return ;}
    int mid=(l+r)>>1;
    if(ql<=mid)query(d[x].l,d[y].l,l,mid,ql,qr);
    if(qr>mid)query(d[x].r,d[y].r,mid+1,r,ql,qr);
}
int main(){
    n=read();len=0;
    inc(i,1,n)a[i]=read();
    inc(i,1,n-1)str[len++]=a[i]-a[i+1],vec.pb(str[len-1]);
    str[len++]=inf;vec.pb(str[len-1]);
    inc(i,2,n)str[len++]=a[i]-a[i-1],vec.pb(str[len-1]);
    str[len++]=-inf;vec.pb(str[len-1]);
    sort(vec.begin(),vec.end());
    sz=unique(vec.begin(),vec.end())-vec.begin();
    for(int i=0;i<len;i++)str[i]=lower_bound(vec.begin(),vec.begin()+sz,str[i])-vec.begin()+1;
    Sa();hh();St();
    for(int i=1;i<len;i++){
	if(sa[i]<n)rt[i]=rt[i-1];
	else{
	    update(rt[i],rt[i-1],1,n,sa[i]-n+1);
	}
    }
    int q=read();
    while(q--){
	int l=read();int r=read();
	if(l==r)printf("%d\n",n-1);
	else{
	    pii ans=solve(rank2[l-1],r-l);
	    if(ans.first>ans.second){printf("0\n");continue;}
	    ans1=0;
	    if(2*l-r-1>=1)query(rt[ans.first-1],rt[ans.second],1,n,1,2*l-r-1);
	    if(n-r+l>r)query(rt[ans.first-1],rt[ans.second],1,n,r+1,n-r+l);
	    printf("%d\n",ans1);
	}
    }
    return 0;
}