RT，T on # 4~12

注释很全，好人一生平安。

听说是要加记忆化，但我寻思我貌似已经加了/kk

听说用map比数组快，但我的程序厌氧，map必然过不去/kk

#include <bits/stdc++.h>
using namespace std;
const int MAX = 5e5 + 7;
struct node
{
	int len, fa;
	int siz;//每个结点对 endpos 集大小的贡献
	int ch[26];
	node()
	{
		len = fa = 0;
		memset(ch, 0, sizeof(ch));
	}
} T[MAX << 1];//SAM结点
struct SAM
{
	int tot = 1, lst = 1;
    
    /*添加字符*/
	void add(int c)
	{
		int p = lst;
		int np = lst = ++tot;
		T[np].siz = 1;
		T[np].len = T[p].len + 1;
		while (p && !T[p].ch[c])
		{
			T[p].ch[c] = np;
			p = T[p].fa;
		}
		if (!p)
		{
			T[np].fa = 1;
		}
		else
		{
			int q = T[p].ch[c];
			if (T[q].len == T[p].len + 1)
			{
				T[np].fa = q;
			}
			else
			{
				int nq = ++tot;
				T[nq] = T[q];
				T[nq].siz = 0;
				T[nq].len = T[p].len + 1;
				T[q].fa = T[np].fa = nq;
				while (p && T[p].ch[c] == q)
				{
					T[p].ch[c] = nq;
					p = T[p].fa;
				}
			}
		}
	}
} Tree;

int kk = 0;

/*本质不同的情况，这部分没有问题*/
namespace st1
{
	int dp[MAX];
	inline void DP(int u)
	{
		if (dp[u])
		{
			return;
		}
		dp[u] = 1;
		for (register int i = 0; i < 26; i++)
		{
			if (T[u].ch[i])
			{
				DP(T[u].ch[i]);
				dp[u] += dp[T[u].ch[i]];
			}
		}
	}
	inline void dfs1(int u, int k)
	{
		k--;
		if (k == 0)
		{
			return;
		}
		for (register int i = 0; i < 26; i++)
		{
			if (T[u].ch[i])
			{

				if (dp[T[u].ch[i]] < k)
				{
					k -= dp[T[u].ch[i]];
				}
				else
				{
					cout << (char)('a' + i);
					kk = 1;
					dfs1(T[u].ch[i], k);
					return;
				}
			}
		}
	}
	void MAIN()
	{
		DP(1);
		int k;
		cin >> k;
		dfs1(1, k + 1);
	}
} // namespace st1

/*不需本质不同的情况*/
namespace st2
{
	int dp2[MAX];//每个结点对应的 endpos 集大小
    
    /*前向星*/
	struct edge
	{
		int next, to;
	} e[MAX << 1];
	int head[MAX], eid = 1;
	inline void adde(int x, int y)
	{
		e[++eid].next = head[x];
		e[eid].to = y;
		head[x] = eid;
	}
    
    /*在parent tree上跑dfs，求出endpos集大小*/
	inline void DP2(int u)
	{
		dp2[u] = T[u].siz;
		for (register int i = head[u]; i; i = e[i].next)
		{
			int v = e[i].to;
			DP2(v);
			dp2[u] += dp2[v];
		}
	}

	int f[MAX];//以u为根的整个子树中的endpos大小之和
    
    /*求子树和*/
	inline void redfs(int u)
	{
		f[u] = dp2[u];
		for (register int i = 0; i < 26; i++)
		{
			if (T[u].ch[i])
			{
				if (!f[T[u].ch[i]])//记忆化，防止重走
				{
					redfs(T[u].ch[i]);
				}
				f[u] += f[T[u].ch[i]];
                //子树和
			}
		}
	}
	inline void dfs2(int u, int k)//跑第k大
	{
		k -= dp2[u];//减去自己
		if (k <= 0)//找到了，则返回
		{
			return;
		}
		for (register int i = 0; i < 26; i++)
		{
			if (T[u].ch[i])
			{
				if (f[T[u].ch[i]] < k)//还不到k，则k减去该子树大小并跳过
				{
					k -= f[T[u].ch[i]];
				}
				else//否则说明第k大在这个子数里，向这个子树搜索
				{
					cout << (char)('a' + i);//输出
					dfs2(T[u].ch[i], k);
					return;
				}
			}
		}
	}
	void MAIN()
	{
		for (register int i = 2; i <= Tree.tot; i++)
		{
			adde(T[i].fa, i);
		}//建parent tree
        
		DP2(1);
		dp2[1] = 0;
        
		int k;
		cin >> k;
        
		redfs(1);
		if (k > f[1])//若全树中的endpos集合大小和都不到k，则必然不存在第k大
		{
			cout << -1;
			return;
		}
		dfs2(1, k);
	}
} // namespace st2
char s[MAX];
signed main()
{
	ios::sync_with_stdio(0);
	cin >> s + 1;
	int len = strlen(s + 1);
	for (register int i = 1; i <= len; i++)
	{
		Tree.add(s[i] - 'a');
	}
	int opt;
	cin >> opt;
	if (opt)
	{
		st2::MAIN();
	}
	else
	{
		st1::MAIN();
	}
}