题目传送门题意给定一个字符串，求每个前缀的字典最大序子串。注意到：对于每个前缀$s_{[1,i]}$，字典序最大子串的右边界一定是\(i\)。随着着\(i\)的增大，字典序最大子串的左边界一定是单调不减的。解法不分先后。后缀数组SASA&SAM后缀数组&后缀自动机SA对所有

前景导入当\(t\in[1,2]\)时，本题如何求解？答：树形dp设\(f[i]\)为以\(i\)为根的树，根节点的晶蝶已消散且儿子节点的晶蝶还未被惊动，能获得的最大晶蝶数。则有状态转移方程\(f[i]=(\sumf[u])+max(a[u])\)，其中\(u\)为\(i\)的儿子。最终的答案即为\(f[1]+a[1]\)划向更

Descirption给出一个排序算法（用伪代码表示）：SORT(A)forifrom1tonforjfrom1tonifa[i]<a[j]Swapa[i]anda[j]算出对于一个序列\(A=a_1,a_2,\cdots,a_n\)的所有前缀\(A_k=a_1,a_2,\cdots,a_k\)（\(1\lek\len\)），\(\operatorname{SORT}(A_

更好的阅读体验很有意思的一道题。设\(f_i\)表示第\(i\)根线的答案，首先有一个关键结论：任意两根相邻的线答案只差一定小于\(1\)。原因显然，可以在无限远的地方加一根线来构造。该结论可以扩展一下，对于距离为\(d\)的两根线，答案之差不会超过\(d\)。考虑进行倒着加线，考虑加

P9842[ICPC2021NanjingR]KleeinSolitaryConfinement你说得对，但是Klee比根号可爱捏题意简述给定\(n,k\)和一个长为\(n\)的序列，你可以选择对区间\([l,r]\)的数整体加上\(k\)，也可以不加。最大化众数出现次数并输出。分析直接做肯定是不好做的，考虑转换思路，考虑区

P9840[ICPC2021NanjingR]Oops,It'sYesterdayTwiceMore注意到最后袋鼠要集中到一个点上，显然先走到四个角落之一再移动到点\((a,b)\)是最优的，可以证明，步数一定不超过\(3(n-1)\)。因为不知道具体要到哪一个角落里，因此记录\((a,b)\)到每个角落的距离并大力分类讨论即可

P9847[ICPC2021NanjingR]Crystalfly你说得对，但是刻晴更可爱捏翻译给定一个\(n(1\len\le10^5)\)个节点的树，每个节点上有\(a_i\)只晶蝶。派蒙最初在\(1\)号节点，并获得\(1\)号节点的所有晶蝶，接下来每一秒她可以移动到相邻的节点上并获得节点上的所有晶蝶，但是当她每到