标签为 [Splay] 的文章

BZOJ1014 [JSOI2008]火星人prefix

题目传送门 大概看了一下题目一脸懵逼,后缀数组?怎么维护修改、插入??仔细看题目好像不是这样的。。。用splay维护字符串,同时维护hash值,然后询问时只要二分+hash判定就好了。时间复杂度O(n lg² n)。主要是代码细节比较多,还有卡常。。。 code #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int p=9875321; int fa[150005],son[150005][2],val[150005],root,mi[150005],n,m,hash[150005],Size[150005]; c ......

BZOJ3786星系探索(DFS序+splay)

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

BZOJ3223 文艺平衡树

题目大意 需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间。并在最后输出整个数列。 Solution 翻转一个区间,显然是Splay的模板题。既然是模板题,题解当然很短…… 只是用了暴力Insert建树的方法,最开始是一条链,效率可能会变低。以后要尽量用build建树的方法。 代码 C++ #include<cstdio> #include<algorithm> using namespace std; int fa[1000010],son[1000010][3],rev[1000010],size[1000010]; int root,cnt; inline void pu ......