【BZOJ 4278】[ONTAK2015] Tasowanie

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4278

解题报告

考虑归并排序
唯一麻烦的地方就是两个字符相同时选哪个
我们可以比较后缀的字典序来解决这个问题
具体实现上,我们可以使用SA

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 800009;
const int SGZ = 1001;

int n, m, s[N];
class Suffix_Array{
int *rk, *tmp, sa[N], bot[N], arr1[N], arr2[N], que[N];
public:
	inline void build(int *s, int nn) {
		rk = arr1; tmp = arr2; int sgz = SGZ;
		for (int i = 1; i <= nn; i++) bot[s[i]]++;
		for (int i = 1; i <= sgz; i++) bot[i] += bot[i - 1];
		for (int i = 1; i <= nn; i++) que[bot[s[i]]--] = i;
		rk[que[1]] = sgz = 1; 
		for (int i = 2; i <= nn; i++) rk[que[i]] = (sgz += s[que[i]] != s[que[i - 1]]);
		for (int l = 1; l < nn && sgz < nn; l <<= 1) {
			int tt = 0;
			for (int i = nn - l + 1; i <= nn; i++) tmp[++tt] = i;
			for (int i = 1; i <= nn; i++) if (que[i] > l) tmp[++tt] = que[i] - l;
			for (int i = 0; i <= sgz; i++) bot[i] = 0;
			for (int i = 1; i <= nn; i++) bot[rk[i]]++;
			for (int i = 1; i <= sgz; i++) bot[i] += bot[i - 1];
			for (int i = nn; i; i--) que[bot[rk[tmp[i]]]--] = tmp[i];
			swap(rk, tmp); rk[que[1]] = sgz = 1;
			for (int i = 2; i <= nn; i++) {
				rk[que[i]] = (sgz += tmp[que[i]] != tmp[que[i - 1]] || tmp[que[i] + l] != tmp[que[i - 1] + l]);
			}
		}
	}
	inline int rank(int p) {
		return rk[p];		
	}
}sa;

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		s[i] = read();
	}
	s[n + 1] = 1001;
	m = read();
	for (int i = 1; i <= m; i++) {
		s[i + n + 1] = read();
	}
	sa.build(s, n + m + 1);
	for (int i = 1, j = 1, k = 1; k <= n + m; k++) {
		if (i <= n && j <= m) {
			if (s[i] < s[j + n + 1] || (s[i] == s[j + n + 1] && sa.rank(i) < sa.rank(j + n + 1))) {
				printf("%d ", s[i++]);
			} else {
				printf("%d ", s[n + 1 + j++]);
			}
		} else if (i <= n) {
			printf("%d ", s[i++]);
		} else {
			printf("%d ", s[n + 1 + j++]);
		}
	}
	return 0;
}

【BZOJ 4650】[NOI2016] 优秀的拆分

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4650
神犇题解:https://blog.sengxian.com/solutions/bzoj-4650

解题报告

主要是统计以每个点为开头/结尾的能划分成两个相等子串的串有多少个
这个是SA的经典应用

当然问能划分成x个相同子串的问题,SA也是一样的做法
比如:https://www.codechef.com/problems/TANDEM

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 60009;
const int SGZ = 26;
const int M = 15;

char pat[N];
int n,c1[N],c2[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

class Suffix_Array{
	char s[N]; int *rak,*que,len,dif;
	int arr1[N],arr2[N],bot[N],sa[N],height[N];
	class Sparse_Table{
		int mn[N][M],len;
		public:
			inline void init(int LEN, int *height) {
				len = LEN; memset(mn,0,sizeof(mn));
				for (int i=1;i<=len;i++) mn[i][0] = height[i];
				for (int j=1,w=1;j<M;j++,w<<=1) {
					for (int i=1,l=len-w;i<=l;i++) {
						mn[i][j] = min(mn[i][j-1], mn[i+w][j-1]);
					}
				} 
			}
			inline int query(int l, int r) {
				if (l > r) swap(l, r); ++l;
				int h = r - l + 1 >> 1, t = 0, L = 1;
				while (L <= h) L<<=1, t++;
				return min(mn[l][t],mn[r-L+1][t]);
			}
	}st;
	public:
		inline void init(char *S, int L) {
			memset(s,0,sizeof(s));
			memset(arr1,0,sizeof(arr1));
			memset(arr2,0,sizeof(arr2));
			for (int i=1;i<=L;i++) s[i] = S[i];
			len = L; build();
		}
		inline int query(int l, int r) {
			if (l < 0 || l > len || r < 0 || r > len) return 0;
			else return st.query(rak[l], rak[r]);
		}
		inline void out() {
			cout<<"----------"<<endl;
			for (int i=1;i<=len;i++) printf("%d ",sa[i]); cout<<endl;
			for (int i=1;i<=len;i++) printf("%d ",height[i]); cout<<endl;
			cout<<"----------"<<endl;
		}
	private:
		inline void build() {
			rak = arr1; que = arr2;
			for (int i=1;i<=SGZ;i++) bot[i] = 0;
			for (int i=1;i<=len;i++) bot[s[i]-'a'+1]++;
			for (int i=2;i<=SGZ;i++) bot[i] += bot[i-1];
			for (int i=1;i<=len;i++) sa[bot[s[i]-'a'+1]--] = i;
			rak[sa[1]] = dif = 1;
			for (int i=2;i<=len;i++) rak[sa[i]] = (dif += (s[sa[i]]!=s[sa[i-1]]));
			for (int l=1,tot;tot=0,l<=len;l<<=1) {
				for (int i=len-l+1;i<=len;i++) que[++tot] = i;
				for (int i=1;i<=len;i++) if (sa[i] > l) que[++tot] = sa[i] - l;
				for (int i=1;i<=dif;i++) bot[i] = 0;
				for (int i=1;i<=len;i++) bot[rak[i]]++;
				for (int i=2;i<=dif;i++) bot[i] += bot[i-1];
				for (int i=len;i;i--) sa[bot[rak[que[i]]]--] = que[i];
				swap(que, rak); rak[sa[1]] = dif = 1;
				for (int i=2;i<=len;i++) 
					if (que[sa[i]]==que[sa[i-1]]&&que[sa[i]+l]==que[sa[i-1]+l]) rak[sa[i]]=dif;
					else rak[sa[i]] = ++dif;
				if (dif >= len) break;
			} 
			for (int i=1;i<=len;i++) {
				int t = max(0, height[rak[i-1]] - 1);
				int p1 = i + t, p2 = sa[rak[i]-1] + t;
				for (;s[p1]==s[p2];p1++,p2++) ++t;
				height[rak[i]] = t;
			}
			st.init(len, height);
		}
}dir,rev; 

int main() {
	for (LL T=read(),vout;vout=0,T;T--) {
		memset(c1,0,sizeof(c1)); memset(c2,0,sizeof(c2));
		scanf("%s",pat+1); n = strlen(pat+1);
		dir.init(pat, n); 
		for (int i=1,j=n;i<j;i++,j--) swap(pat[i], pat[j]);
		rev.init(pat, n);
		for (int l=1,suf,pre,L,R;l<=n;l++) {
			for (int i=1;i<=n;i+=l) {
				suf = dir.query(i, i+l); 
				pre = rev.query(n-i+2, n-i-l+2) + 1;
				L = max(i, i + l - pre);
				R = min(i + l - 1, i + suf - 1);
				if (L <= R) {
					c1[L+l]++; c1[R+l+1]--;
					c2[L-l]++; c2[R-l+1]--;
				}
			}
		}
		for (int i=1,t1=c1[0],t2=c2[0];i<=n;i++) {
			t1 += c1[i]; t2 += c2[i];
			vout += (LL)t1 * t2;
		}
		printf("%lld\n",vout);
	}
	return 0;
}

【LA 5524】[EC2015 Final] Suffixes and Palindromes

相关链接

题目传送门:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5524

题目大意

给出一个串的$sa$数组和$manacher$求出的那个数组
请你构造出一个字典序最小的符合条件的串,可能无解

有$T(T \le 100)$组数据
数组长度$\le 10^5$
时间限制:$4s$

背景

Claris给我安利的题,似乎子问题都会的样子
但合起来就不会了

解题报告

考虑$manacher$的那个数组,实际上是给出了$O(n)$条信息
每一条信息形如:第$i$个字符(不)等于第$j$个字符
如果只有这个条件的话,我们可以搞成几个大连通块,然后贪心

考虑$sa$数组,上午才做了这个题
也可以直接贪心

但这两货直接合在一起,似乎是给出一个差分约束系统
然后让你输出一组可行解,还要让你字典序最小
于是就不会了

但我们还是考虑直接在$SA$数组上贪心
考虑回文等价的影响的话,那实际上是填一位就会影响后面的很多位
似乎想一想,直接贪心会不会使一个区间的两头被值域给卡住
但仔细想一想,即使你给那一个等价类一个大一点的字符,区间的差分序列没有变啊
该卡住的还是会卡住,没被卡住的也不会有问题

于是我们任然在SA数组上贪心,考虑能不能与前一个数相等的时候
不仅考虑$rank$数组的影响,我们还需要考虑回文等价的影响
于是这题就这么做完啦,仍然是一个$O(n)$的贪心

【BZOJ 4319】[CERC2008] Suffix Reconstruction

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4319
神犇题解:http://www.cnblogs.com/Skyminer/p/6414088.html

解题报告

之前在做这个题的时候就听说过这题
但当时想了一会儿,感觉不可做,以为是他们记错题目了 QwQ
今天居然看到原题了,但想了很久,还是只会$O(26 \cdot n \log{n})$

先来说说$O(26 \cdot n \log{n})$的做法吧!
我们可以从上到下单个字符填,就是尽量往小的填,填完以后$O(n)$验证一遍

我们考虑分出不同的地方,因为填了都是比他小的,所以如果冲突,那一定是之前的太大了
但之前的部分已经贪心尽量小地填了,所以之前的肯定不能改小了,只能把当前位改大

所以这么做是对的,时间复杂度:$O(26 \cdot n^2)$
不难发现$SA$数组上一定是一段连续的A,之后一段连续的B。后面也是这样
于是我们可以二分每一个字符地分界点,这样复杂度就是$O(26 \cdot n \log{n})$的了

正解的话,是$O(n)$的,仍然是从小到大贪心
我们考虑计算$height$数组时候那个Trick的正确性证明
如果$rank[sa[i]+1] > rank[sa[i+1]+1]$的话,那么$sa[i]$填的字符一定比$sa[i+1]$小
否则他俩相等也没有关系,因为后面还是会把他们区分出来
于是贪心就可以$O(1)$验证了,于是总的时间复杂度就是线性的了!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500009;

int n,sa[N],rak[N];
char ans[N];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main() {
	n = read(); 
	for (int i=1;i<=n;i++) rak[sa[i]=read()]=i;
	ans[sa[1]] = 'a';
	for (int i=1,w='a';i<n;i++) (rak[sa[i]+1]>rak[sa[i+1]+1])? ans[sa[i+1]]=++w: ans[sa[i+1]]=w;
	if (ans[n] <= 'z') printf("%s",ans+1);
	else puts("-1");
	return 0;
}

【日常小测】Different Trips

题目大意

给定一棵$n(n \le 10^5)$个结点的树,每一个结点的特征值定义为这个结点的度
询问从根节点走到叶子结点的所有路径中本质不同的字符串的数量

解题报告

这题就是诸神眷顾的幻想乡的弱化版,撸一发广义SAM就可以了

不过GEOTCBRL考完之后给我们增加了一点姿势水平:

广义后缀自动机如果使用DFS建立的话,时间复杂度是$O($叶子结点深度和$)$的
如果使用BFS来建立的话,时间复杂度是$O(n \cdot$字符集大小$)$

这在15年刘研绎的集训队论文《后缀自动机在字典树上的拓展》中有详细的证明
其中还给出了构造极端数据的构造方法
所以这题字符集大小这么大的话,这样会T的
可能只有后缀数组才能做 QwQ

Code

这辣鸡代码是可以卡的,泥萌不要卡啊…….

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 2000009;
 
int n,head[N],nxt[N],to[N],in[N];
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
 
inline void AddEdge(int u, int v) {
    static int E = 1; in[u]++; in[v]++;
    to[++E] = v; nxt[E] = head[u]; head[u] = E;
    to[++E] = u; nxt[E] = head[v]; head[v] = E;
}
 
class Suffix_Automaton{
    int tot,len[N],fail[N],vis;
    map<int,int> ch[N];
    public:
        inline Suffix_Automaton() {tot=1;}
        inline int insert(int t, int c) {
            if (ch[t]&&len[ch[t]]==len[t]+1) return ch[t];
            int w = ++tot; len[w] = len[t] + 1;
            for (;t&&!ch[t];t=fail[t]) ch[t] = w;
            if (!t) fail[w] = 1;
            else if (len[ch[t]] == len[t] + 1) fail[w] = ch[t];
            else {
                int nt = ++tot, pt = ch[t];
                ch[nt] = ch[pt]; len[nt] = len[t] + 1;
                fail[nt] = fail[pt]; fail[pt] = fail[w] = nt;
                for (;t&&ch[t]==pt;t=fail[t]) ch[t] = nt;
            } return w;
        }
        inline LL GetAns() {
            LL ret = 0;
            for (int i=2;i<=tot;i++)
                ret += len[i] - len[fail[i]];
            return ret;
        }
}SAM;
 
void DFS(int w, int f, int ins) {
    int nins = SAM.insert(ins, in[w]);
    for (int i=head[w];i;i=nxt[i]) {
        if (to[i] != f) {
            DFS(to[i], w, nins);
        }
    }
}
 
int main() {
    n = read();
    for (int i=1;i<n;i++) AddEdge(read(), read());
    DFS(1, 1, 1);
    printf("%lld\n",SAM.GetAns());
    return 0;
}

【BZOJ 4199】[NOI2015] 品酒大会

相关链接

题目传送门Ⅰ:http://uoj.ac/problem/131
题目传送门Ⅱ:http://www.lydsy.com/JudgeOnline/problem.php?id=4199
神犇题解:https://blog.sengxian.com/solutions/bzoj-4199

解题报告

其实sengxian都写了题解了,我还有什么写的意义 _(:з」∠)_
不过还是简单说两句吧!

我们考虑把SA建出来,height数组搞出来
然后把height数组排个序
从小到大依次合并上去就可以辣!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 600009; 
const LL INF = 1e18;

int n,val[N],sz[N],mx[N],mn[N]; 
int height[N],bot[N],sa[N],arr[N];
int *rak,*que,arr1[N],arr2[N],fa[N];
char pat[N]; LL ans1,ans2;
stack<pair<LL,LL> > ans;

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline bool cmp(const int &a, const int &b) {
	return height[a] > height[b];
}

class Suffix_Array{
	public:
		inline void build() {
			rak = arr1; que = arr2;
			for (int i=1;i<=n;i++) bot[pat[i]-'a'+1]++;
			for (int i=1;i<=26;i++) bot[i] += bot[i-1];
			for (int i=1;i<=n;i++) sa[bot[pat[i]-'a'+1]--] = i;
			for (int ty=0,i=1;i<=n;i++) rak[sa[i]] = pat[sa[i]]==pat[sa[i-1]]? ty: ++ty;
			for (int l=1,tot=0,ty;l<n;l<<=1,tot=0) {
				memset(bot,0,sizeof(bot));
				for (int i=n-l+1;i<=n;i++) que[++tot] = i;
				for (int i=1;i<=n;i++) if (sa[i]>l) que[++tot] = sa[i] - l;
				for (int i=1;i<=n;i++) bot[rak[i]]++;
				for (int i=1;i<=n;i++) bot[i] += bot[i-1];
				for (int i=n;i;i--) sa[bot[rak[que[i]]]--] = que[i];
				swap(rak, que); rak[sa[1]] = ty = 1; bot[1] = 1;
				for (int i=2;i<=n;i++) 
					if (que[sa[i]] == que[sa[i-1]] && que[sa[i]+l] == que[sa[i-1]+l]) rak[sa[i]] = ty;
					else bot[rak[sa[i]] = ++ty] = 0;
				if (ty >= n) break;
			}
			Get_Height();
		}
		inline void solve() { 
			for (int i=1;i<=n;i++) {
				arr[i] = fa[i] = i; sz[i] = 1; 
				mn[i] = mx[i] = val[sa[i]];
			}
			sort(arr+1, arr+1+n, cmp);
			for (int i=n-1,j=1;~i;i--) {
				for (;height[arr[j]]>=i;++j) update(arr[j]);
				ans.push(make_pair(ans1, ans2));
			} 
			for (;!ans.empty();ans.pop()) 
				printf("%lld %lld\n",ans.top().first, ans.top().second);
		}	
	private:
		inline void Get_Height() {
			for (int i=1,len,p1,p2;i<=n;i++) {
				len = max(height[rak[i-1]] - 1, 0);
				p1 = i + len; p2 = sa[rak[i]-1] + len;
				while (pat[p1] == pat[p2]) ++p1, ++p2, ++len;
				height[rak[i]] = len;
			} height[1] = -1;
		}
		int find(int x) {return fa[x]==x?x:find(fa[x]);}
		inline void update(int i) { 
			static int E = 1; if (E) E = 0, ans2 = -INF;
			int f1 = find(i), f2 = find(i-1);
			ans1 += (LL)sz[f1] * sz[f2];
			ans2 = max(ans2, (LL)mx[f2] * mx[f1]);
			ans2 = max(ans2, (LL)mn[f2] * mn[f1]);
			sz[f1] += sz[f2]; fa[f2] = f1;
			mx[f1] = max(mx[f1], mx[f2]);
			mn[f1] = min(mn[f1], mn[f2]);
		}
}SA;

int main() {
	n = read();
	scanf("%s",pat+1);
	for (int i=1;i<=n;i++) val[i] = read();
	SA.build();
	SA.solve();
	return 0;
}

—————————— UPD 2017.7.10 ——————————
显然这货用SAM也是可做的

【日常小测】最长公共前缀

题目大意

给定一棵以$1$号点为根、大小为$n$的有根树($n \le 10^5$),每一条边上有一个小写英文字母
给定$m$个询问,第$i$个询问包含一个长度为$t_i$的点集(元素可重,$\sum{t_i} \le 2 \cdot 10^5$),询问$\sum\limits_{a=1}^{t_i}{\sum\limits_{b=a+1}^{t_i}{lcp(a,b)}}$

定义$s_a$为从a出发走向根,将边上的字符按顺序写下来构成的字符串
定义$lcp(a,b)$为$s_a$与$s_b$的最长公共前缀

下面举一个栗子
若树长成这样:

那么$s_5=cb,s_4=cbb$
更进一步,若某次询问的点集为$\{4,5\}$那么答案为$2$

解题报告

看到这种树上的字符串,我能想到AC自动机,或者广义后缀自动机
想了想AC自动机做不了,那就广义后缀自动机来做咯!

考虑后缀自动机上的Fail树
一个点的祖先实际上是这个点代表的字符串的后缀
那么题目中的$lcp(a,b)$就变成了$lca(a,b)$
于是对于每一次询问,我们建一个虚树出来
然后在虚树上DFS一次,统计一下答案就好啦!

另外,这题用后缀数组也可以做!
听武爷讲一讲,大概就是先把Trie树建出来
同时记录下每一次倍增的$Rank$数组(波兰表……)
然后就正常倍增,写法已经和罗穗骞的后缀数组的实现很不同了

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 200009;
const int M = N << 1;
 
int n,m,E,head[N],nxt[M],to[M],col[M],pos[N],id[N];
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
 
inline void Add_Edge(int u, int v, int c = 0) {
    to[++E] = v; nxt[E] = head[u]; head[u] = E; col[E] = c;
    to[++E] = u; nxt[E] = head[v]; head[v] = E; col[E] = c;
}   
 
class Suffix_Automaton{
	int cnt=1,ch[N][26],fail[N],vis[N],dep[N],sum[N];
	int tot,arr[N],que[N],len[N],fa[N][20],_hash[N];
	vector<int> G[N]; LL ans_tmp;
    public:
        inline int insert(int t, int cc) {
            if (ch[t][cc] && len[ch[t][cc]] == len[t] + 1) return ch[t][cc];
            int tail = ++cnt; len[tail] = len[t] + 1;
            while (!ch[t][cc] && t) ch[t][cc] = tail, t=fail[t];
            if (!t) fail[tail] = 1;
            else {
                if (len[ch[t][cc]] == len[t] + 1) fail[tail] = ch[t][cc];
                else {
                    int nw = ++cnt, w = ch[t][cc]; len[nw] = len[t]+1;
                    memcpy(ch[nw], ch[w], sizeof(ch[nw]));
                    fail[nw] = fail[w]; fail[w] = fail[tail] = nw;
                    for (;ch[t][cc]==w;t=fail[t]) ch[t][cc] = nw;
                }
            } return tail;
        }
        inline void Build_Fail_Tree() {
            memset(head,0,sizeof(head)); E = 0;
            for (int i=2;i<=cnt;i++) Add_Edge(fail[i], i);
            dfs(1, 1);
            for (int j=1;j<20;j++) {
                for (int i=1;i<=cnt;i++) {
                    fa[i][j] = fa[fa[i][j-1]][j-1];
                }
            }   
        }
        inline LL solve(int nn) {
            for (int i=1;i<=nn;i++) arr[i] = pos[read()];
            sort(arr+1, arr+1+nn, [](const int &a, const int &b) {return id[a] < id[b];});
            for (int i=1;i<=nn;i++) _hash[i] = arr[i];
            int mm = nn; nn = unique(arr+1, arr+1+nn) - arr - 1;
            for (int i=1;i<=nn;i++) sum[i] = 0;
            for (int i=1,j=1;i<=mm;i++) {
                while (arr[j] != _hash[i]) j++;
                sum[j]++;
            }
            que[tot=1] = 1; int MX = 1;
            for (int i=1,lca;i<=nn;i++) {
                vis[arr[i]] = sum[i];
                lca = LCA(que[tot], arr[i]);
                while (dep[que[tot]] > dep[lca]) {
                    if (dep[que[tot-1]] >= dep[lca]) G[que[tot-1]].push_back(que[tot]);
                    else G[lca].push_back(que[tot]);
                    --tot;
                }
                if (que[tot] != lca) que[++tot] = lca;
                if (arr[i] != que[tot]) que[++tot] = arr[i];
                MX = max(MX, tot);
            }
            while (tot > 1) G[que[tot-1]].push_back(que[tot]), --tot;
            ans_tmp = 0;
            Get_Ans(1);
            return ans_tmp;
        }
    private:
        void dfs(int w, int f) {
            static int id_count = 0;
            id[w] = ++id_count;
            fa[w][0] = f; dep[w] = dep[f] + 1;
            for (int i=head[w];i;i=nxt[i]) {
                if (to[i] != f) {
                    dfs(to[i], w);
                }
            }
        } 
        int Get_Ans(int w) {
            int ret = vis[w]; 
            if (w > 1) ans_tmp += vis[w] * (vis[w] - 1ll) / 2 * len[w]; 
            for (int i=G[w].size()-1,tmp;~i;i--) { 
                tmp = Get_Ans(G[w][i]);
                ans_tmp += (LL)tmp * ret * len[w];
                ret += tmp;
            }
            vis[w] = 0; 
            G[w].clear();
            return ret;
        }
        inline int LCA(int a, int b) {
            if (dep[a] < dep[b]) swap(a, b);
            for (int i=19;~i;i--) if (dep[fa[a][i]] >= dep[b]) a = fa[a][i];
            if (a == b) return a;
            for (int i=19;~i;i--) if (fa[a][i] != fa[b][i]) a = fa[a][i], b = fa[b][i];
            return fa[a][0];
        }   
}SAM;
 
void DFS(int w, int f, int t) {
    pos[w] = t;
    for (int i=head[w];i;i=nxt[i]) {
        if (to[i] != f) {
            int nt = SAM.insert(t, col[i]);
            DFS(to[i], w, nt);
        }
    }
}
 
int main() {
    n = read(); char pat[10];
    for (int i=1,u,v;i<n;i++) {
        u = read(); v = read();
        scanf("%s",pat+1);
        Add_Edge(u, v, pat[1] - 'a');
    }   
    DFS(1, 1, 1);
    SAM.Build_Fail_Tree();
    for (int i=read();i;i--) 
        printf("%lld\n",SAM.solve(read()));
    return 0;
}

【BZOJ 4556】[TJOI2016&HEOI2016] 字符串

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4556
神犇题解:http://www.cnblogs.com/Var123/p/5575518.html

解题报告

这个题目实际上是询问 $s(c,d)$ 的 $LCP$
于是我们考虑二分这个长度 $L$
那么这个 $L$ 就相当于在 $SA$ 的数组上划了一个区间
不难发现如果这个区间中存在一个后缀的起点属于 $s(a,b)$ ,这个长度就是合法的
于是我们二分一下,然后搞一个后缀数组和函数式线段树就可以啦!

【BZOJ 4516】[SDOI2016] 生成魔咒

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4516

考试的时候,一看到要动态维护就把SA扔一边凉快去了QAQ
想一想,不能这么草率啊!
来说一说SA和SAM两种做法

1) SAM:
很明显就是求一个字符串本质不同的字串个数
SAM本身就是增量构造,于是就成裸题了

2) SA:
考虑离线之后,先逆序建一个完整的出来
那么加入一个字符,实际上就是加入了一个后缀
那么其对于答案的贡献,就是原来的height数组搞一搞
实现的话,搞一个RMQ什么的就好
代码的话,我们来召唤Menci:https://oi.men.ci/sdoi2016-incantation/

自己太懒,于是就只写了SAM的代码:

#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define LL long long
using namespace std;
using namespace tr1;

const int N = 200000+9; 

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

namespace Suffix_Automaton{
	#define SAM Suffix_Automaton
	int len[N],fail[N],cnt,tail;
	unordered_map<int,int> ch[N]; 
	
	inline int Extend(int c) {
		int w = tail; tail = ++cnt; len[tail] = len[w] + 1;
		while (w&&!ch[w]) ch[w] = cnt, w = fail[w];
		if (!w) fail[tail] = 1;
		else {
			if (len[ch[w]] == len[w]+1) fail[tail] = ch[w];
			else {
				int to = ch[w]; ch[++cnt] = ch[to];
				fail[cnt] = fail[to]; fail[to] = cnt; fail[tail] = cnt; 
				len[cnt] = len[w] + 1; while (ch[w] == to) ch[w] = cnt, w = fail[w];
			}
		} return len[tail] - len[fail[tail]];
	}
	
	inline void solve(int n) {
		cnt = tail = 1; 
		for (LL i=1,vout=0;i<=n;i++) 
			printf("%lld\n",vout+=Extend(read()));
	}
};

int main(){
	SAM::solve(read());
	return 0;
}

—– UPD 2016.9.29 —–
这™map比unordered_map快这么多有几个意思QAQ
475864785645
这种感觉……
真·生无可恋
V5[YANBJ`4%A2`%PIH$BH_F