题目传送门 大概看了一下题目一脸懵逼,后缀数组?怎么维护修改、插入??仔细看题目好像不是这样的。。。用splay维护字符串,同时维护hash值,然后询问时只要二分+hash判定就好了。时间复杂度O(n lg² n)。主要是代码细节比较多,还有卡常。。。 code #include<cstdio …

题目传送门 n个点,n-1条边而且没有环,所以这是一棵有根树。看到要修改连边,以为是Link-Cut tree,可是又要子树修改和链查询。。。好像行不通。由于这是一棵根节点固定的有根树,考虑DFS序。记录每一个点u的入栈时间戳in[u]和出栈时间戳out[u],任意一个在以u为根的子树中的节点v,都 …

题目大意 需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间。并在最后输出整个数列。 Solution 翻转一个区间,显然是Splay的模板题。既然是模板题,题解当然很短…… 只是用了暴力Insert建树的方法,最开始是一条链,效率可能会变低。以后要尽量用b …