題目鏈接：點擊查看

題目大意：給出一個長度為 $n$ 的字符串，再給出 $q$ 次詢問，每次詢問需要輸出本質不同第 $k$ 小的子串的起止位置。如果有多個答案，輸出起點最小的那個。

本題規定字符串大小的比較規則如下：

首先按照長度排序

長度相同的情況下，按字典序排序

題目大意：

首先還是利用后綴自動機將后綴樹建出來，此時長度為 $d$ 的本質不同的子串，可以用深度為 $d$ 的所有節點集合表示出來。

因為后綴樹上的邊都是經過壓縮的，所以每條邊實質上代表的是許多連續的前綴。

所以我們需要枚舉深度 $d$，利用差分數組，類比于掃描線的思想，維護一下當前深度所有節點。

上面只是討論了深度不同的情況，對于深度相同的情況，可以參考題目 HDU - 5008 Boring String Problem(后綴樹求本質不同第k大子串) ，跑出后綴樹的 $dfs$ 序，不難發現對于同層的節點來說，$dfs$ 序更小的節點對應著字典序更小。

更具體的，我們需要維護一個數據結構，可以滿足下面的條件：

維護一個線性表

按照 $dfs$ 序排序

支持插入/刪除一個元素

支持查詢第 $k$ 小的元素

支持實時統計元素個數

通過分析之后可以發現上面的數據結構可以用平衡樹來寫，也可以用線段樹來寫。

然后將詢問離線下來，碼就完事了，時間復雜度是 $O((n+q)\log n)$

2021.11.14 UPDATE：

Memory limit exceeded on test 11，是我寫的太丑了么。

2021.11.14 RE-UPDATE：

卡了卡內存A掉了，具體體現在 dfs 里少了一個 vector。

代碼：（只過了樣例，等題目上傳到 gym 后會更新）

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10); putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+5; char s[N]; vector<int>node[N<<1]; int tot,last,endpos[N<<1]; int dfn[N<<1],rk[N<<1],cnt; vector<int>delta[N]; pair<LL,int>q[N]; int ansl[N],ansr[N]; namespace SEG {struct Node {int l,r,sum;}tree[N<<1<<2];void pushup(int k) {tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;}void build(int k,int l,int r) {tree[k]={l,r,0};if(l==r) return;int mid=(l+r)>>1;build(k<<1,l,mid),build(k<<1|1,mid+1,r);}void update(int k,int pos,int val) {if(tree[k].l==tree[k].r) {tree[k].sum=val;return;}int mid=(tree[k].l+tree[k].r)>>1;if(pos<=mid) update(k<<1,pos,val);else update(k<<1|1,pos,val);pushup(k);}int query(int k,int x) {if(tree[k].l==tree[k].r) {return tree[k].l;}if(x<=tree[k<<1].sum) return query(k<<1,x);else return query(k<<1|1,x-tree[k<<1].sum);}void push(int x) {update(1,dfn[x],1);}int kth(int k) {return rk[query(1,k)];}void pop(int x) {update(1,dfn[x],0);}int size() {return tree[1].sum;} } struct Node {int ch[26];int fa,len; }st[N<<1]; inline int newnode() {tot++;for(int i=0;i<26;i++)st[tot].ch[i]=0;st[tot].fa=st[tot].len=0;endpos[tot]=0;node[tot].clear();return tot; } void add(int x) {int p=last,np=last=newnode();st[np].len=st[p].len+1;while(p&&!st[p].ch[x])st[p].ch[x]=np,p=st[p].fa;if(!p)st[np].fa=1;else{int q=st[p].ch[x];if(st[p].len+1==st[q].len)st[np].fa=q;else{int nq=newnode();st[nq]=st[q]; st[nq].len=st[p].len+1;st[q].fa=st[np].fa=nq;while(p&&st[p].ch[x]==q)st[p].ch[x]=nq,p=st[p].fa;//向上把所有q都替換成nq}} } void dfs_pos(int u) {for(auto v:node[u]) {dfs_pos(v);endpos[u]=max(endpos[u],endpos[v]);} } void dfs(int u) {dfn[u]=++cnt;rk[cnt]=u;sort(node[u].begin(),node[u].end(),[&](int x,int y) {return s[endpos[x]-st[u].len]<s[endpos[y]-st[u].len];});for(auto v:node[u]) {delta[st[u].len+1].push_back(v);delta[st[v].len+1].push_back(-v);dfs(v);} } void build() {for(int i=1;i<=tot;i++) {node[st[i].fa].push_back(i);}dfs_pos(1);dfs(1); } void init() {last=1;cnt=tot=0;newnode(); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);scanf("%s",s+1);init();int n=strlen(s+1);reverse(s+1,s+1+n);for(int i=1;i<=n;i++) {add(s[i]-'a');endpos[last]=i;}build();int m;scanf("%d",&m);for(int i=1;i<=m;i++) {read(q[i].first);q[i].second=i;ansl[i]=ansr[i]=-1;}sort(q+1,q+1+m);LL sum=0;int p=1;SEG::build(1,1,tot);for(int d=1;d<=n;d++) {//deepfor(auto it:delta[d]) {if(it>0) SEG::push(it);else SEG::pop(-it);}LL pre=sum;sum+=SEG::size();while(p<=m&&q[p].first>pre&&q[p].first<=sum) {LL k=q[p].first;int id=q[p].second;int u=SEG::kth(k-pre);ansl[id]=n-endpos[u]+1;ansr[id]=ansl[id]+d-1;p++;}}for(int i=1;i<=m;i++) {printf("%d %d\n",ansl[i],ansr[i]);}return 0; } 超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的2021CCPC(桂林) - Suffix Automaton(后缀树+线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。