洛谷P10716【MX-X1-T4】「KDOI-05」简单的字符串问题（扩展kmp+set+二分+扫描线树状数组）

题目

思路来源

小羊肖恩

题解

羊神这个做法tql，当时只是机械地写，过了之后再想想，才觉得确实是nb

先扩展kmp（Z函数）预处理出来数组，记z[i]为i往后可以和前缀匹配的最大长度

对于每个询问(p,cnt)，先离线归位到每个p所在的vector内，

然后扫描线，每个i有一个[i,i+z[i]-1]的区间，在这个区间内以j结尾时，和前缀的lcp固定为[i,j]

对于每个i，先特判只出现一次的情况

对于大于一次的情况，先二分当前最大的可行长度x，

这个需要预处理mn[i][j]表示前i个字符出现j次时的结尾处的最小下标，没有的话就是n+1

对于位置p，出现次数cnt，二分找到满足mn[x][cnt]<=p的最大x，

长度x的前缀出现了cnt次，那么短于长度x的前缀一定出现了cnt次，

然后[i,i+z[i]-1]的扫描线保证了以p结尾的一定是一个当前合法的A串，

这就保证了A在开头和结尾均出现，且总的出现次数不少于cnt次了

一开始暴力双指针预处理mn超时了，后来改成在set上二分就ac了

因为长的串对应的位置一定包含短串，所以可以按zi从大到小释放位置，放进set，在set里二分

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10;
struct BitPre{ // 求前缀和(可改为max等)
	int n,tr[N];
	void init(int _n){
		n=_n;
		memset(tr,0,(n+1)*sizeof(*tr));
	}
	void add(int x,int v){
		++x;
		for(int i=x;i<=n;i+=i&-i)
		tr[i]+=v;
	}
	int sum(int x){
		++x;
		int ans=0; 
		for(int i=x;i;i-=i&-i)
		ans+=tr[i];
		return ans;
	}
}tr;
int n,m,net[N],ans[N];
char s[N];
P ask[N];
vector<int>q[N],add[N],del[N],mn[N];
void extkmppre(char s[],int len){
	int i=0,j,pos;
	net[0]=len;
	while(i+1<len&&s[i]==s[i+1])i++;
	net[1]=i,pos=1;
	rep(i,2,len-1){
		if(net[i-pos]+i<net[pos]+pos){
			net[i]=net[i-pos];
		}
		else{
			j=net[pos]+pos-i;
			if(j<0)j=0;
			while(i+j<len&&s[j]==s[i+j])j++;
			net[i]=j,pos=i;
		}
	}
}
void init(){
	set<int>S;
	vector<vector<int> >in(n+1,vector<int>());
	rep(i,0,n-1){
		in[net[i]].pb(i);
	}
	per(i,n,1){
		for(auto &x:in[i]){
			S.insert(x);
		}
		int up=n/i+1;
		mn[i].resize(up);
		mn[i][0]=0;
		mn[i][1]=i-1;
		//printf("i:%d up:%d\n",i,up);
		rep(j,2,up-1){
			if(mn[i][j-1]>n){
				mn[i][j]=n+1;
				continue;
			}
			auto it=S.upper_bound(mn[i][j-1]);
			if(it==S.end()){
				mn[i][j]=n+1;
			}
			else{
				mn[i][j]=(*it)+i-1;
			}
			//printf("i:%d j:%d mn:%d\n",i,j,mn[i][j]);
		}
	}
	rep(i,0,n-1){
		add[i].pb(i);
		del[i+net[i]-1].pb(i);
	}
}
bool ok(int len,int cnt,int p){
	if(!len)return 1;
	if(1ll*len*cnt>p+1)return 0;
	return mn[len][cnt]<=p;
	//printf("len:%d ok:%1d\n",len,o);
	//"cnt:%d p:%d mn:%d net:%d\n",len,cnt,p,mn[len][cnt],net[p-len+1]);
	//return o;
}
int main(){
	sci(n);
	scanf("%s",s);
	extkmppre(s,n);
	// rep(i,0,n-1){
		// printf("i:%d z[i]:%d\n",i,net[i]);
	// }
	init();
	tr.init(n+1);
	sci(m);
	rep(i,1,m){
		sci(ask[i].fi);
		sci(ask[i].se);
		ask[i].fi--;
		q[ask[i].fi].pb(i);
	}
	rep(i,0,n-1){
		for(auto &x:add[i]){
			tr.add(x,1);
		}
		for(auto &x:q[i]){
			int p=ask[x].fi,c=ask[x].se;
			if(c==1){
				ans[x]=1;
				continue;
			}
			int l=0,r=n;
			while(l<=r){
				int mid=(l+r)/2;
				if(ok(mid,c,i))l=mid+1;
				else r=mid-1;
			}
			//printf("id:%d p:%d c:%d len:%d\n",x,p,c,r);
			if(r==0)ans[x]=0;
			else ans[x]=tr.sum(i)-tr.sum(i-r);
			// rep(j,1,i){
				// printf("%d ",tr.sum(j)-tr.sum(j-1));
			// }
			// puts("");
		}
		for(auto &x:del[i]){
			tr.add(x,-1);
		}
	}
	rep(i,1,m){
		printf("%d\n",ans[i]);
	}
	return 0;
}