codeforces round #741 div2 E.Rescue Niwen!（sam

题目链接：https://codeforces.ml/contest/1562/problem/E

题意：

求最长上升子串序列长度，上升条件为：子串字典序严格递增 以及 子串起点非严格递增，详见题目样例解释。

思路历程：

只会sam，所以刚开始就直接往sam上想了，对于同起点的子串不好表示，将串翻转，建立sam，易得，每个节点表示的子串集在所有（原）子串中的字典序排名是连续的，比如某节点表示的子串集有edcb,dcb,cb,因为是翻转，所以其原子串为，bc,bcd,bcde，显然是连续的。接下来我们需要求出所有节点的排名，具体方式为，遍历后缀树，遍历子树之前，对所有孩子排序，优先遍历字典序小的孩子，这样遍历得到的dfn序即为所有节点的排名，详见代码。
得到所有节点排名之后，进行dp，dp[i]含义为，以排名为i的子串为结尾时最长上升长度，转移方程为， 若当前子串排名为x, 则 i从x+1遍历到n,dp[i]=max(dp[i],dp[x]+len);len的含义为当前节点子串集大小, 即 sam[now].len-sam[sam[now].fa].len
转移方式只满足字典序上升，因此我们还需 从后往前遍历所有子串，（即原串的从前往后），遍历以某位置为起点的所有子串方式为，找到以当前下标结束的最长子串节点位置（建sam时可标记），然后递归跳到fa处，直到fa为空节点，回溯时更新dp数组以及答案。
这样的状态转移方式需要线段树更新（我想不到别的方法），当字符串全为a时会跑满复杂度，
n方log，所以考虑优化，考虑到dp数组是递增的，所以我们更新时，只要暴力更新x+1到孩子的排名就行了，不难得到这样是o(n)的，因此整体复杂度为n方的。详见代码

代码：

#include <bits/stdc++.h> 
using namespace std;
#define ford(i,a,n) for(i=a;i<=n;i++)
#define forb(i,n,a) for(i=n;i>=a;i--)
#define mst(a) memset(a,0,sizeof(a))
#define maxn 10010
struct hzzdj{
	int len,fa,nex[26];
}sam[maxn<<1];//sam
int last=1;
int num=1;
int endpos[maxn];//以某个下标为结尾的子串集在sam中是哪个节点
void add(int c,int pos)
{
	int p=last;
	int nowp=last=++num;
    endpos[pos]=num;//在这里得到就行了
	sam[nowp].len=sam[p].len+1;
	while(p&&!sam[p].nex[c])
	{
		sam[p].nex[c]=nowp;
		p=sam[p].fa;
	}
	if(!p)
	sam[nowp].fa=1;
	else
	{
		int q=sam[p].nex[c];
		if(sam[q].len==sam[p].len+1)
		sam[nowp].fa=q;
		else
		{
			int nowq=++num;
			sam[nowq]=sam[q];
			sam[nowq].len=sam[p].len+1;
			sam[q].fa=sam[nowp].fa=nowq;
			while(p&&sam[p].nex[c]==q)
			{
				sam[p].nex[c]=nowq;
				p=sam[p].fa;
			}
		}
	}
}//建机方式套板子
int gochar[maxn];
int fa[maxn];//这两个数组在比较两个节点字典序大小时会用到
void dfs2(int now,int c,int f)
{
    int i;
    if(fa[now])
    return;
    gochar[now]=c;//稍微熟悉sam的朋友应该知道，节点表示的子串集为后缀关系，那么在原串中为前缀关系
    fa[now]=f;//这里的fa不是后缀树父亲，为串的上一个节点，任意一个都可
    ford(i,0,25)
    if(sam[now].nex[i])
    dfs2(sam[now].nex[i],i,now);
}
int cnt;
int cmp(int a,int b)
{
    while(1)
    {
        if(gochar[a]!=gochar[b])
        return gochar[a]<gochar[b];
        a=fa[a];
        b=fa[b];
    }//暴力判断两个串大小
    return 1;//无用
}
int rdfn[maxn];//dfn序
int q[maxn][31];//一个节点最多26个孩子，遍历排序时用到，在递归时开数组也行
int first[maxn];
int nex[maxn];
int go[maxn];
int amount;//邻接表，构建后缀树
void addedge(int u,int v)
{
    go[++amount]=v;
    nex[amount]=first[u];
    first[u]=amount;
}
void dfs(int now)
{
    if(now>1)
    rdfn[now]=++cnt;//dfn序
    int i;
    int temp=0;
    for(i=first[now];i;i=nex[i])
    q[now][++temp]=go[i];//对孩子排序
    sort(q[now]+1,q[now]+temp+1,cmp);
    ford(i,1,temp)
    dfs(q[now][i]);//遍历孩子
}
int ans;//答案
int c[maxn];//dp数组
void getans(int now,int ed)
{
    if(now==1)
    return;
    getans(sam[now].fa,rdfn[now]);//先遍历父亲，因为当前串可由父亲串转移
    int temp=c[rdfn[now]]+sam[now].len-sam[sam[now].fa].len;//转移结果
    ans=max(ans,temp);//更新答案
    int i;
    ford(i,rdfn[now]+1,ed)
    c[i]=max(c[i],temp);//更新x+1到父亲的排名的dp值
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//ddd;
    int test;
    cin>>test;
    while(test--)
    {
        int i;
        ford(i,1,num)
        mst(sam[i].nex),sam[i].len=sam[i].fa=fa[i]=go[i]=first[i]=c[i]=0;
        num=last=1;
        cnt=amount=ans=0;//初始化
        int n;
        cin>>n;
        string s;
        cin>>s;
        reverse(s.begin(),s.end());//翻转
        ford(i,0,n-1)
        add(s[i]-'a',i+1);//建机
        dfs2(1,-1,0);
        ford(i,2,num)
        addedge(sam[i].fa,i);//构建后缀树
        dfs(1);//得到排名
        forb(i,n,1)
        getans(endpos[i],num-1);//从后往前遍历更新dp数组
        cout<<ans<<endl;
    }
}

不懂私聊