ZigZagK的博客
[后缀数组+离线+扫描线+线段树二分]2021 CCPC 桂林 J【Suffix Automaton】题解
[后缀数组+离线+扫描线+线段树二分]2021 CCPC 桂林 J【Suffix Automaton】题解
2021年11月17日 17:13
CCPC
查看标签

题目概述

Suffix Automaton

解题报告

被时限骗了,以为做法是两个 $\log$(空间爆炸),其实只要离线就可以一个 $\log$ 。

求出后缀数组后,第 $i$ 个后缀多出来的就是 $[SA_i,SA_i+H_i\sim n]$ 共 $n-(SA_i+H_i)+1$ 个子串。对应的长度区间是 $[H_i+1,n-SA_i+1]$ 。

如果用主席树就可以实现动态查找第 $K$ 小,但是这样是两个 $\log$ ,而且空间复杂度爆炸了。

由于第 $i$ 个点出现在 $[H_i+1,n-SA_i+1]$ 长度区间中,我们可以在 $H_i+1$ 插入 $i$ ,在 $n-SA_i+2$ 删除 $i$ ,用扫描线+线段树维护每个长度对应的后缀位置。因此考虑离线,将询问从小到大排序后从小到大考虑长度。

设当前长度为 $i$ ,$cnt$ 表示 $[1,i-1]$ 长度子串个数,$sum$ 表示长度为 $i$ 子串个数,那么如果 $cnt<K\le cnt+sum$ 就说明第 $K$ 小子串的长度为 $i$ ,然后在线段树里二分第 $K-cnt$ 小就可以得知对应位置。

由于要求出答案子串第一次出现的位置,还需要在后缀数组上二分一下,然后求出符合区间中最靠前的位置。

示例程序

  • 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
#include<cstdio> #include<cctype> #include<algorithm> #define fr first #define sc second #define mp make_pair using namespace std; typedef long long LL; const int maxn=1000000,maxt=maxn<<2,LOG=20; int te,n;char s[maxn+5]; int Q,ans[maxn+5][2];pair<LL,int> q[maxn+5]; int SA[maxn+5],rk[maxn+5],t[(maxn<<1)+5],ha[maxn+5]; int H[maxn+5],RMQ[maxn+5][LOG+1],MIN[maxn+5][LOG+1],lg[maxn+5]; int m;pair<int, pair<int,int> > a[(maxn<<1)+5]; int sum[maxt+5]; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); lst=='-'?x=-tot:x=tot;return EOLN(ch); } int reads(char *s){ int len=0;char ch=readc(); while (!islower(ch)) ch=readc(); while (islower(ch)) s[++len]=ch,ch=readc(); s[len+1]=0;return len; } template<typename T> void writei(T x){ static int len=0,buf[100]; if (x<0) putchar('-'),x=-x; do buf[len++]=x%10,x/=10; while (x); while (len) putchar(buf[--len]+48); } void Sort(int n,int m){ for (int i=0;i<=m;i++) ha[i]=0;for (int i=1;i<=n;i++) ha[rk[i]]++; for (int i=1;i<=m;i++) ha[i]+=ha[i-1];for (int i=n;i;i--) SA[ha[rk[t[i]]]--]=t[i]; } #define min(x,y) ((x)<(y)?(x):(y)) void Make(int n,int m=255){ for (int i=1;i<=n;i++) rk[i]=s[i],t[i]=i,t[i+n]=0;Sort(n,m); for (int k=1,p=0;p<n;m=p,k<<=1){ p=0;for (int i=n-k+1;i<=n;i++) t[++p]=i; for (int i=1;i<=n;i++) if (SA[i]>k) t[++p]=SA[i]-k; Sort(n,m);for (int i=1;i<=n;i++) t[i]=rk[i];rk[SA[1]]=p=1; for (int i=2;i<=n;i++) rk[SA[i]]=(p+=t[SA[i-1]]!=t[SA[i]] || t[SA[i-1]+k]!=t[SA[i]+k]); } for (int i=1,k=0;i<=n;i++){ if (k) k--; while (s[i+k]==s[SA[rk[i]-1]+k]) k++; H[rk[i]]=k; } H[1]=0; for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1; for (int i=1;i<=n;i++) RMQ[i][0]=H[i],MIN[i][0]=SA[i]; for (int j=1;(1<<j)<=n;j++) for (int i=1;i+(1<<j)-1<=n;i++) RMQ[i][j]=min(RMQ[i][j-1],RMQ[i+(1<<j-1)][j-1]), MIN[i][j]=min(MIN[i][j-1],MIN[i+(1<<j-1)][j-1]); } int LCP(int L,int R){ L++;int k=lg[R-L+1]; return min(RMQ[L][k],RMQ[R-(1<<k)+1][k]); } int Min(int L,int R){ int k=lg[R-L+1]; return min(MIN[L][k],MIN[R-(1<<k)+1][k]); } void Insert(int pos,int k,int l=1,int r=n,int p=1){ sum[p]+=k;if (l==r) return; int mid=l+(r-l>>1); pos<=mid?Insert(pos,k,l,mid,p<<1):Insert(pos,k,mid+1,r,p<<1|1); } int Find(int k,int l=1,int r=n,int p=1){ if (l==r) return l; int mid=l+(r-l>>1); return k<=sum[p<<1]?Find(k,l,mid,p<<1):Find(k-sum[p<<1],mid+1,r,p<<1|1); } int main(){ n=reads(s);Make(n); for (int i=1;i<=n;i++) if (H[i]<n-SA[i]+1) a[++m]=mp(H[i]+1,mp(i,1)),a[++m]=mp(n-SA[i]+2,mp(i,-1)); sort(a+1,a+1+m); readi(Q);for (int i=1;i<=Q;i++) readi(q[i].fr),q[i].sc=i; sort(q+1,q+1+Q); LL cnt=0; for (int i=1,j=1,k=1;i<=n && k<=Q;i++){ while (j<=m && a[j].fr==i) Insert(a[j].sc.fr,a[j].sc.sc),j++; while (k<=Q && q[k].fr<=cnt+sum[1]){ int p=Find(q[k].fr-cnt); int L=1,R=p-1; for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) LCP(mid,p)>=i?R=mid-1:L=mid+1; int ql=L; L=p+1;R=n; for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) LCP(p,mid)>=i?L=mid+1:R=mid-1; int qr=R; ans[q[k].sc][0]=Min(ql,qr);ans[q[k].sc][1]=ans[q[k].sc][0]+i-1; k++; } cnt+=sum[1]; } for (int i=1;i<=Q;i++) if (ans[i][0]) writei(ans[i][0]),putchar(' '),writei(ans[i][1]),puts(""); else puts("-1 -1"); return 0; }
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
本文写于 1230 天前,最后更新于 1230 天前。
部分信息可能已经过时,博主也可能已经无法对其内容进行解答。
OK
  1. 1 Skyscape Plum - Melodic Artist
  2. 2 ほしのおとしもの ああああ
  3. 3 感情の摩天楼 ~ Cosmic Mind 上海アリス幻樂団
  4. 4 秘匿されたフォーシーズンズ 上海アリス幻樂団
  5. 5 Ideal and the Real 小西利樹
  6. 6 Undertale Toby Fox
  7. 7 First Steps Lena Raine
  8. 8 Mirror Temple (Mirror Magic Mix) Lena Raine / 2 Mello
  9. 9 City of Tears Christopher Larkin
  10. 10 Tower Of Heaven (You Are Slaves) Feint
Skyscape - Plum - Melodic Artist
00:00 / 00:00
An audio error has occurred, player will skip forward in 2 seconds.

作曲 : Jeong Min Jae

纯音乐,请欣赏