[Str记录]P5108 仰望半月的夜空

**题意** : 给出字符串 $S$。 对于每个 $i$ ，求出长为 $i$ 的，字典序最小的子串的最小的左端点。 $S\leq 3\times 10^5$ ，字符集 $10^7$ ，时限$\texttt{1s}$。 ------------ 简单题。 考虑后缀树，在上面 $\rm dfs$ 即可按照字典序访问各个子串。 记 $s_u$ 为节点 $u$ 子树中最小的左端点。不难发现，后缀树的每条压缩边中的 $s$ 的值相同。 于是问题转化为 ： 将一个区间未被赋值的答案赋值为 $x$ 。用并查集维护即可。 用 `std::map` 建立后缀树。复杂度为 $O(n\log n)$。 这里写的是 $\rm SAM$ 建立后缀树。 ```cpp #include<algorithm> #include<cstdio> #include<vector> #include<map> #define pb push_back #define ull unsigned long long #define Itor map<int,int>::iterator #define MaxN 300500 using namespace std; struct Node{map<int,int> t;int len,f,ed;}a[MaxN<<1]; int tn,las; void add(int c) { int np=++tn,p=las;las=np; a[np].len=a[p].len+1; for (;p&&!a[p].t[c];p=a[p].f)a[p].t[c]=np; if (!p)a[np].f=1; else { int v=a[p].t[c]; if (a[v].len==a[p].len+1)a[np].f=v; else { int nv=++tn;a[nv]=a[v]; a[nv].len=a[p].len+1; for (;p&&a[p].t[c]==v;p=a[p].f)a[p].t[c]=nv; a[np].f=a[v].f=nv; } } } vector<int> g[MaxN<<1]; int n; void dfs(int u) { if (!a[u].ed)a[u].ed=n+1; for (int i=0;i<g[u].size();i++){ dfs(g[u][i]); a[u].ed=max(a[u].ed,a[g[u][i]].ed); } } struct CovDS { int f[MaxN],ans[MaxN]; void Init() {for (int i=1;i<=n+1;i++)f[i]=i;} int find(int u) {return f[u]==u ? u : f[u]=find(f[u]);} void merge(int u,int v){f[find(u)]=find(v);} void cov(int l,int r,int x) {for (int p=find(l);p<=r;p=find(p)){ans[p]=x;merge(p,p+1);}} void print() {for (int i=1;i<=n;i++)printf("%d ",n-ans[i]+1);} }T; void dfs2(int u) { if (u>1)T.cov(a[a[u].f].len+1,a[u].len,a[u].ed); for (Itor it=a[u].t.begin();it!=a[u].t.end();it++) dfs2(it->second); } int op,x[MaxN]; char s[MaxN]; int main() { scanf("%d%d",&op,&n); if (op==26){ scanf("%s",s+1); for (int i=1;i<=n;i++)x[i]=s[i]; }else for (int i=1;i<=n;i++)scanf("%d",&x[i]); reverse(x+1,x+n+1); las=tn=1; for (int i=1;i<=n;i++){add(x[i]);a[las].ed=i;} for (int i=2;i<=tn;i++)g[a[i].f].pb(i); dfs(1); for (int i=1;i<=tn;i++)a[i].t.clear(); for (int i=2;i<=tn;i++){ int fa=a[i].f; a[fa].t[x[a[i].ed-a[fa].len]]=i; } T.Init();dfs2(1);T.print(); return 0; } ```