洛谷 P4143 採集礦石後綴數組

2021 年 2 月 10 日
筆記
字元串, 二分查找

題目背景

ZRQ 成功從坍塌的洞穴中逃了出來。終於，他看到了要研究的礦石。他想挑一些帶回去完成任務。

題目來源：Zhang_RQ哦對了 \(ZRQ\) 就他，嗯

題目描述

ZRQ 發現這裡有 \(N\) 塊排成一排的礦石。

他用一個小寫字母來表示每塊礦石，他還發現每塊礦石有一個重要度 \(V_i\)。

ZRQ 想採集一段連續的礦石回研究所。

他非常嚴格，被採集的一段礦石必須滿足小寫字母的字典序降序排名等於這段礦石的重要度和。

這裡多個出現在不同位置的本質相同串的字典序排名相同。

比如說字母串為 aa，那麼第一個 a 的排名和第二個 a 的排名相同，都是 2（第 1 是 aa）。

ZRQ 問你，在原串中有哪些不同的子串可以被採集？

這裡子串不同定義為出現位置不同，也就是說本質相同的子串出現在不同位置都要計算一次（當然重要度和等於排名是前提）。

比如共有 \(4\) 塊礦石，小寫字母串為 abcd，重要度各為 10 0 1 1。

我們把所有的子串按照字典序從大到小排名：1:d 2:cd 3:c 4:bcd 5:bc 6:b 7:abcd 8:abc 9:ab 10:a。

那麼串 d 的排名為 \(1\)（第一大），重要度和為 \(1\)，可以被採集。

串 cd 的排名為 \(2\)，重要度和為 \(2\)，可以被採集。

串 a 的排名為 \(10\)，重要度和為 \(10\)，可以被採集。

其他串則不滿足這個條件，故有三個串可以被採集。

輸入格式

第一行一個長度為 \(N\) 由小寫字母組成的字元串，每個字元代表一個礦石。

第二行 \(N\) 個整數，表示 \(V_i\)。

輸出格式

一行一個整數，表示能被採集的子串個數 \(S\)。

接下來 \(S\) 行每行兩個整數 \(L,R\)，分別表示每個可採集子串的左端點與右端點，按照左端點升序為第一關鍵字，右端點升序為第二關鍵字排序。

輸入輸出樣例

輸入 #1

abcd
10 0 1 1

輸出 #1

輸入 #2

aaaa
1 1 1 1

輸出 #2

輸入 #3

aaa
1 1 1

輸出 #3

2
1 2
2 3

輸入 #4

aaa
1 1 2

輸出 #4

1
1 2

說明/提示

共 \(10\) 個測試點，每個點 \(10\) 分，計 \(100\) 分。

對於所有測試點，有 \(N\leq 10^5\)，\(0 \le V_i \le 1000\)。保證每個點可被採集的子串不超過 \(10^5\) 個。

樣例#1解釋放在題面里了。

樣例#2解釋：

每個子串都不滿足條件。

串 a 的排名是 \(4\)，重要度和都是 \(1\)。

串 aa 的排名是 \(3\)，重要度和都是 \(2\)。

串 aaa 的排名是 \(2\)，重要度和都是 \(3\)。

串 aaaa 的排名是 \(1\)，重要度和都是 \(4\)。

樣例 #3解釋：

串 a 的排名是 \(3\)，重要度和都是 \(1\)。

串 aa 的排名是 \(2\)，重要度和都是 \(2\)，共有兩個串aa，位置分別為 \(1 \sim 2\) 和 \(2 \sim3\)。

串 aaa 的排名是 \(1\)，重要度和都是 \(3\)。

樣例 #4解釋：

可以發現，串 \(2 \sim 3\)（第二個 aa）不滿足條件了。它的排名還是 \(2\) 不變，但是重要度和為 \(3\)。

分析

前置知識：後綴數組

要求出所有排名等於重要度的子串並輸出方案

首先可以證明這樣的子串不會超過 \(n\) 個

因為假如我們固定了左端點，那麼隨著右端點的增大，重要度不會變小，但是排名會變小

因此對於一個確定的左端點，最多只會有一個右端點滿足條件

又因為重要度和排名都是單調的，所以只需要固定左端點，二分合法的右端點就可以了

考慮如何快速求出一個子串的重要度和排名

重要度可以用前綴和 \(O(1)\) 查詢

排名可以用後綴數組求出

在計算一個字元串的本質不同的子串時，我們會用到一個式子

\(\sum_{i=1}^nn-sa[i]+1-height[i]\)

一個很有用的性質就是這樣求出的本質不同字串是按順序的

所以對於一個子串，只需要算出它的前面有多少本質不同的子串即可

先用一個數組記錄一下這個式子的前綴和，然後分情況討論

設 \(fir[i]\) 為 \(i\) 號後綴的排名

如果 \(len \geq height[fir[l]]\)，那麼排名為 \(sum_{fir[l]}-(n-r)\)

否則向前二分找到一個位置 \(pos\)，使得它恰好滿足 \(len \geq height[pos]\)，那麼排名為 \((sum_{pos}-(n-sa[pos]-len+1))\)

後面減去的那一部分是左端點相同但是長度比當前子串長的

因為排名是按照字典序從大到小來的，所以還要拿總的本質不同的子串減去求出的結果

時間複雜度 \(O(nlog^2n)\)

程式碼

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}	
const int maxn=1e5+5;
int sa[maxn],fir[maxn],sec[maxn],tax[maxn],n,heig[maxn],lg[maxn],mmin[maxn][20],m;
int a[maxn],sum1[maxn],sta1[maxn],sta2[maxn],tp;
char s[maxn];
long long tot,sum2[maxn];
void Qsort(){
	for(rg int i=0;i<=m;i++) tax[i]=0;
	for(rg int i=1;i<=n;i++) tax[fir[i]]++;
	for(rg int i=1;i<=m;i++) tax[i]+=tax[i-1];
	for(rg int i=n;i>=1;i--) sa[tax[fir[sec[i]]]--]=sec[i];
}
void getsa(){
	m=1e5;
	for(rg int i=1;i<=n;i++) fir[i]=s[i],sec[i]=i;
	Qsort();
	for(rg int len=1,p=0;p<n;len<<=1,m=p){
		p=0;
		for(rg int i=n-len+1;i<=n;i++) sec[++p]=i;
		for(rg int i=1;i<=n;i++) if(sa[i]>len) sec[++p]=sa[i]-len;
		Qsort();
		memcpy(sec,fir,sizeof(sec));
		fir[sa[1]]=p=1;
		for(rg int i=2;i<=n;i++) fir[sa[i]]=(sec[sa[i]]==sec[sa[i-1]] && sec[sa[i]+len]==sec[sa[i-1]+len])?p:++p;
	}
}
void getheight(){
	rg int j,k=0;
	for(rg int i=1;i<=n;i++){
		if(k) k--;
		j=sa[fir[i]-1];
		while(s[i+k]==s[j+k]) k++;
		heig[fir[i]]=k;
	}
	tot=1LL*n*(n+1)/2LL;
	for(rg int i=2;i<=n;i++) tot-=heig[i];
	for(rg int i=1;i<=n;i++) sum2[i]=sum2[i-1]+n-sa[i]+1-heig[i];
}
void pre(){
	for(rg int i=1;i<=n;i++) mmin[i][0]=heig[i];
	for(rg int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
	for(rg int j=1;j<=18;j++){
		for(rg int i=1;i+(1<<j)-1<=n;i++){
			mmin[i][j]=std::min(mmin[i][j-1],mmin[i+(1<<(j-1))][j-1]);
		}
	}
}
int getans(rg int l,rg int r){
	l++;
	rg int k=lg[r-l+1];
	return std::min(mmin[l][k],mmin[r-(1<<k)+1][k]);
}
int getval(rg int l,rg int r){
	return sum1[r]-sum1[l-1];
}
long long getrk(rg int l,rg int r){
	rg int len=r-l+1;
	if(heig[fir[l]]<=len) return tot-(sum2[fir[l]]-(n-r))+1;
	rg int nl=1,nr=fir[l]-1,mids;
	while(nl<=nr){
		mids=(nl+nr)>>1;
		if(getans(mids,fir[l])<=len) nl=mids+1;
		else nr=mids-1;
	}
	return tot-(sum2[nr]-(n-sa[nr]-len+1))+1;
}
void solve(rg int id){
	rg int l=id,r=n,mids;
	while(l<=r){
		mids=(l+r)>>1;
		if(getrk(id,mids)==getval(id,mids)){
			sta1[++tp]=id,sta2[tp]=mids;
			return;
		} else if(getrk(id,mids)>getval(id,mids)){
			l=mids+1;
		} else {
			r=mids-1;
		}
	}
}
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	for(rg int i=1;i<=n;i++) a[i]=read();
	getsa(),getheight(),pre();
	for(rg int i=1;i<=n;i++) sum1[i]=sum1[i-1]+a[i];
	for(rg int i=1;i<=n;i++) solve(i);
	printf("%d\n",tp);
	for(rg int i=1;i<=tp;i++) printf("%d %d\n",sta1[i],sta2[i]);
	return 0;
}

Tags: 字元串二分查找