列表

详情

NC216001. Baby'sFirstSuffixArrayProblem

描述

A suffix array for string s of length n is a permutation sa of integers from 1 to n such that is the list of non-empty suffixes of s sorted in lexicographical order. The rank table for suffixex of s is a permutation rank of integers from 1 to n such that .

Kotori has a string . She would like to ask m queries. And in the i-th query, a substring of s is given, Kotori would like to know the rank of suffix of x.

Note means the substring of s which starts from the l-th position and ends at the r-th position, both inclusive.

输入描述

There are multiple test cases. The first line of the input contains an integer T indicating the number of test cases. For each test case:

The first line contains two integers n and m () -- the length of the string and the number of queries.

The second line contains a string s of length n consisting only of lowercase English letters.

Each of the next m lines contains three integers l_i, r_i and k_i () denoting a query.

It is guaranteed that neither the sum of n or the sum of m of all test cases will exceed .

输出描述

For each query output one line containing one integer denoting the answer.

示例1

输入: 

2
10 4
baaabbabba
2 8 3
1 1 1
2 3 2
2 5 4
20 3
cccbccbadaacbbbcccab
14 17 16
3 20 17
17 20 18

输出: 

2
1
2
3
4
15
3

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++11) 解法, 执行用时: 785ms, 内存消耗: 65756K, 提交时间: 2020-12-21 16:56:28 

#include<bits/stdc++.h>
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define rep(i,l,r) for (int i=l;i<=r;++i)
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;

const int N=100005;
char s[N];
int x[N],y[N],SA[N],rk[N],n,Q;
int lg[N],cnt[N],hei[N][20];

int cmp(int i,int j,int k){
	return y[i]!=y[j]||((i+k>n)?-1:y[i+k])!=(j+k>n?-1:y[j+k]);
}
void build_SA(){
	int m=26;
	For(i,0,m) cnt[i]=0;
	For(i,1,n) cnt[x[i]=s[i]-'a'+1]++;
	For(i,1,m) cnt[i]+=cnt[i-1];
	Rep(i,n,1) SA[cnt[x[i]]--]=i;
	for (int k=1;k<n;k<<=1){
		int p=0;
		For(i,n-k+1,n) y[++p]=i;
		For(i,1,n) if (SA[i]>k) y[++p]=SA[i]-k;
		For(i,0,m) cnt[i]=0;
		For(i,1,n) cnt[x[y[i]]]++;
		For(i,1,m) cnt[i]+=cnt[i-1];
		Rep(i,n,1) SA[cnt[x[y[i]]]--]=y[i];
		
		For(i,0,n+2) swap(x[i],y[i]);
		m=x[SA[1]]=1;
		For(i,2,n) x[SA[i]]=(m+=cmp(SA[i-1],SA[i],k));
	}
	For(i,1,n) rk[SA[i]]=i;
	For(i,2,n) lg[i]=lg[i/2]+1;
	int p=0;
	For(i,1,n) if (rk[i]!=1){
		p-=(p!=0);
		for (;s[i+p]==s[SA[rk[i]-1]+p];++p);
		hei[rk[i]][0]=p;
	}
	For(i,1,16) For(j,1,n-(1<<i)+1)
		hei[j][i]=min(hei[j][i-1],hei[j+(1<<(i-1))][i-1]);
}

const int M=5000005;

int ls[M],rs[M],S[M];
int rt[N],nd;

void insert(int &nk,int k,int l,int r,int p){
	nk=++nd; S[nk]=S[k]+1;
	ls[nk]=ls[k]; rs[nk]=rs[k];
	if (l==r) return;
	int mid=(l+r)/2;
	if (p<=mid) insert(ls[nk],ls[k],l,mid,p);
	else insert(rs[nk],rs[k],mid+1,r,p);
}
int ask(int k,int l,int r,int x,int y){
	if (x<=l&&r<=y) return S[k];
	int mid=(l+r)/2;
	if (y<=mid) return ask(ls[k],l,mid,x,y);
	if (x>mid) return ask(rs[k],mid+1,r,x,y);
	return ask(ls[k],l,mid,x,y)+ask(rs[k],mid+1,r,x,y);
}
int query_1(int p,int l,int r){
	return l<=r?ask(rt[p],1,n,l,r):0;
}
int rmq(int x,int y){
	int k=lg[y-x+1];
	return min(hei[x][k],hei[y-(1<<k)+1][k]);
}
int find_l(int x,int len){
	x=rk[x];
	int l=1,r=x-1,p=x;
	while (l<=r){
		int mid=(l+r)/2;
		if (rmq(mid+1,x)>=len)
			p=mid,r=mid-1;
		else l=mid+1;
	}
	return p;
}
int find_r(int x,int len){
	x=rk[x];
	int l=x+1,r=n,p=x;
	while (l<=r){
		int mid=(l+r)/2;
		if (rmq(x+1,mid)>=len)
			p=mid,l=mid+1;
		else r=mid-1;
	}
	return p;
}
namespace BFD
{
#define PB push_back
#define int long long
#define PII pair<int,int> 
 #define FI first
 #define SE second
 #define R(i,n) for(int i=0;i<n;i++)
 #define ALL(x) (x).begin(),(x).end()
 #define SZ(x) ((int)(x).size())
 #define MAX 50010
 struct ciag{
 int a,il,b;
 ciag(){}
 ciag(int _a,int _il,int _b){a=_a,il=_il,b=_b;}
 inline bool add(int x){
 if(il==1){
 b=x - a;
 il=2;
 return 1;
 }
 if(a+il*b==x){
 il++;
 return 1;
 }
 return 0;
 }
 inline int ost(){return a+(il- 1)*b;}
 };
 int exgcd(int a,int b,int&x,int&y){
 if(a<b)return exgcd(b,a,y,x);
 if(b==0)return x=1,y=0,a;
 int t,d=exgcd(b,a%b,t,x);
 return y=t- x*(a/b),d;
 }
 inline int floordiv(int a,int b){
 if(b<0)a= -a,b= -b;
 int d=a/b,m=a- d*b;
 if(m<0)d--;
 return d;
 }
 inline int ceildiv(int a,int b){
 int r=floordiv(a,b);
 if(a%b)r++;
 return r;
 }
 inline ciag marek(ciag&a,ciag&b){
 ciag wynik;
 int n,m,da=b.a- a.a,g=exgcd(a.b,b.b,n,m);
 if(da%g)return ciag(1,0,1);
  n*=da/g;
wynik.b=a.b/g*b.b;
int elem=a.a+a.b*n,maxA=a.ost(),maxB=b.ost(),
minIle=max(ceildiv(a.a- elem,wynik.b),ceildiv(b.a -elem,wynik.b)),
maxIle=min(floordiv(maxA- elem,wynik.b),floordiv(maxB- elem,wynik.b));
if(minIle>maxIle)return ciag(1,0,1);
wynik.a=elem+minIle*wynik.b;
wynik.il=maxIle -minIle+1;
return wynik;
}
vector<vector<ciag> >ciagi[MAX];
int n,kmr[19][MAX];
vector<pair<PII,int> >x;
char *z;
vector<int>wys[MAX];
inline void mapuj(int j){
sort(ALL(x));
int id=0;
R(i,SZ(x)){
if(i&&x[i- 1].FI!=x[i].FI)id++;
kmr[j][x[i].SE]=id;
wys[id].PB(x[i].SE);
}
ciagi[j].resize(id+1);
R(i,id+1){
for(vector<int>::iterator it=wys[i].begin();it!=wys[i].end();it++)
if(ciagi[j][i].empty()||!ciagi[j][i].back().add(*it))
ciagi[j][i].PB(ciag(*it,1,0));
wys[i].clear();
}
}
inline void licz_kmr(){
R(i,n)x.PB(pair<PII,int>(PII(z[i],0),i));
mapuj(0);
int krok=1,j=0;
while(krok<n){
x.clear();
R(i,n -krok)x.PB(pair<PII,int>(PII(kmr[j][i],kmr[j][i+krok]),i));
mapuj(++j);
krok<<=1;
}
}
inline int pierw(int j,int k,int x){
int l= -1,r=SZ(ciagi[j][k]);
while(l+1!=r){
int m=(l+r)>>1;
 if(ciagi[j][k][m].ost()>=x)r=m;else l=m;
 }
 return r;
 }
 inline ciag przetnij(ciag xx,ciag y,int a,int b,int k){
 xx.a=b -xx.ost();
 y.a=k+y.a -a;
 if(xx.il==1)xx.b=1;
 if(y.il==1)y.b=1;
 return ciag(marek(xx,y));
 }
 int ans;
 inline void spr(int a,int b,int j){
 int k=1<<j,aa=kmr[j][a],bb=kmr[j][b -k],pa=pierw(j,aa,b -2*k),pbb=pierw(j,bb,a);
 while(pa<SZ(ciagi[j][aa])){
 if(ciagi[j][aa][pa].a>b- k)break;
 int pb=pbb;
 while(pb<SZ(ciagi[j][bb])){
 if(ciagi[j][bb][pb].a>a+k)break;
 ciag pom=przetnij(ciagi[j][aa][pa],ciagi[j][bb][pb],a,b,k);
 if(pom.il!=0){
	 int lim=min(2*k,b-a-1);
	 int en=pom.ost();
	 if(en>lim)
	 {
		 pom.il-=(en-lim+pom.b-1)/pom.b;
	 	 en=pom.ost();
	 }
     lim=k+1-(k==1);
	 for(int i=0;en>=lim && i<pom.il;++i,en-=pom.b)
	 {
		 ans+=rk[b-en+1]>rk[a+1];
//		 fprintf(stderr,"%lld %lld %lld\n",en,b-en+1,a+1);
	 }
 }
 pb++;
 }
 pa++;
 }
 }
 inline int zap(int a,int b){
 int j=0,dl=b- a;
 while((1<<(j+1))<dl)j++;
 ans=0;
// rep(i,a,b-1)fprintf(stderr,"%c",z[i]);
// fprintf(stderr,"\n");
 while(~j){spr(a,b,j);j--;}
// fprintf(stderr,"\n");
 return ans;
 }
 #undef int
 void init(char *s,int _n)
 {
	 z=s;n=_n;
	 rep(i,0,n){ciagi[i].clear();wys[i].clear();rep(j,0,18)kmr[j][i]=0; }
	 x.clear();
	licz_kmr();	
 }
};
void solve(){
	scanf("%d%d",&n,&Q);
	scanf("%s",s+1);
	build_SA();
	BFD::init(s+1,n);	
	nd=0;
	For(i,1,n)
		insert(rt[i],rt[i-1],1,n,SA[i]);
	For(i,1,Q){
		int l,r,x;
		scanf("%d%d%d",&l,&r,&x);
		int pl=find_l(x,r-x+1);
		int res=query_1(pl-1,l,x-1)+1;
		res+=query_1(rk[x],x+1,r);
		res+=BFD::zap(x-1,r);
		cout<<res<<endl;
	}
}
int main(){
#ifdef kcz
	freopen("1.in","r",stdin);
	freopen("0.out","w",stdout);
#endif
	int T;
	scanf("%d",&T);
	while (T--) solve();
}

上一题

© 2025 nowcoder.com