标签为 [数据结构] 的文章

[BZOJ2006]超级钢琴

题目大意 从一个序列中,找出k段连续的子序列,且每个子序列的长度不小于L,不大于R。 一个序列的权值定义为序列中所有数的和,求k个子序列和的最大值。具体看原题。 Solution 这道题应该用主席树来做,但是太麻烦。相比起来,ST表+堆的算法显然比较方便(可能我代码写得太丑)。 考虑每次取出一段最大的合法的子序列,这样取k次。第一次取的时候,如果枚举了一个右端点r,那么r-R+1<=l<=r-L+1。 如果用前缀和sum数组表示这个区间的和,就是sum[r]-sum[l-1]。当r固定时,l也在一个固定的区间内变化,只要sum[l]取这个区间中的 ......

关于并查集单用按秩合并的分析

1.按秩合并的操作 相信大家都知道并查集(不相交集合森林),由于路径压缩优化后时间复杂度分析极难,不易理解,本文来讨论下一种易于分析的优化方式:按秩合并。按秩合并的时间复杂度是O(lgn)的,常数很小,虽然不是特别优秀,但在许多情况下也够用了。 按秩合并的方式就是,对于每一个结点x记录下一个秩(x.rank),表示结点x的高度。每次链接的时候将rank值小的结点的父亲指向rank值大的结点,如果两者秩一样,就随便链哪一个。伪代码: link(x,y) if x.rank&gt;y.rank y.parent ......

BZOJ3123 森林

题目大意 给一个森林,森林有n个节点m条边。 现在有两种操作: Q x y k 表示询问x-y这条链上点权的第k小。保证x,y在同一个连通块里。 L x y 表示链接x,y两点。保证x,y在不同的连通块里。 总共有T次操作,要求强制在线,last表示上一次的答案,每次x,y,k都要异或last.last初始为0. 对于所有的数据,n,m,T<=8*10^4 . Solution 因为有连接两个点的操作,所以xqj大神一眼就报出了题解:LCT。 可是我这个菜鸡怎么都想不出LCT的做法。因为还要询问点权的第k小,还要在splay上套一棵线段树。用树套树维护LCT,反正我是不会。但我相 ......

BZOJ2743 采花

题目大意 有n个数,每个数一种颜色。m次询问,每次询问l,r区间内除去只有一个数的颜色的不同颜色的种数。 n,m<=1000,000 Solution 刚看到题目,就想到了一种非常方便的莫队做法。看了一眼数据范围,发现要$10^9$的复杂度,卡一卡就过去了。 我会函数式线段树,于是有口胡了一个可持久化线段树的做法,就是维护出所有1~r的线段树,且1~i+1的线段树是从1~i的线段树修改几个点后继承过来的。花了10分钟写完,开数组时发现要开三个2e7的数组,空间240MB,而内存限制只有128MB,不得已,砍掉一半,数组大小定了1e7。交上去后,喜闻乐 ......

BZOJ1014 [JSOI2008]火星人prefix

题目传送门 大概看了一下题目一脸懵逼,后缀数组?怎么维护修改、插入??仔细看题目好像不是这样的。。。用splay维护字符串,同时维护hash值,然后询问时只要二分+hash判定就好了。时间复杂度O(n lg² n)。主要是代码细节比较多,还有卡常。。。 code #include&lt;cstdio&gt; #include&lt;cstring&gt; #include&lt;algorithm&gt; 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]]。观察可得,在这条链上的点的入栈时间戳一定在这段区间内,出栈时间 ......

BZOJ1015 [JSOI2008]星球大战starwar

题目传送门 明天星球大战8就要在中国上映了,然后今天就来做一下这道题(纯属扯淡) 好了,现在来看这道题。 求联通块的个数,想到用并查集来维护。可是,并查集只能完成加边,不能完成删边的。那怎么办?然后发现题目中只有删点,没有加点,而且没有强制在线,所以想到可以离线做,把删点操作倒过来做,就成了加点了,这就可以用并查集维护了。 code #include&lt;stdio.h&gt; #include&lt;cmath&gt; #include&lt;algorithm&gt; #include&lt;cstdlib&gt; #include ......

BZOJ5020在美妙的数学王国中畅游

题目传送门 Solution 在每次询问的x是固定时,可以用LCT维护出一条链上的所有函数的和。而x不固定,该怎么办呢? 其实可以用泰勒展开表示一个函数在某个点上的值。即:$f(x)=\sum_{k=0}^{n}\frac{f^{(k)}(x0)}{k!}(x-x0)^k+\frac{f^{(n+1)}(\xi)}{(n+1)!}{(x-x0)}^{n+1}$ 其中,x0是任意取的一个数,而后面的余项是用来估计误差值的,因为只能计算前面的式子,当余项很小的时候,这个误差就会变小。当n>=15时,这个误差值会小于$1e-7$。 对于具体的这些函数: $f^{(0)}(x)=\sin(ax+b)$, $f^{(k)}(x)=-f^{(k-2)}(x)*a^2$ $f^{(0) ......

HihoCoder1034毁灭者问题

题目大意 假设你拥有 n 个魔法单位,他们从左到有站在一行,编号从 1 到 n。 每个单位拥有三项属性: si: 初始法力。 mi: 最大法力上限。 ri: 每秒中法力回复速度。 现在你操纵一个毁灭者,有 m 个操作,t l r,表示时刻 t,毁灭者对所有编号从 l 到 r 的单位,使用了魔法吸收。操作按照时间顺序给出,计算毁灭者一共吸收了多少法力。 Solution 这题其实有很多做法。可以计算每此操作的答案,也可以计算每个单位的总答案。 如果能维护出每个单位i的所有操作的时间点的序列,并算出操作两两之间的时间差。那么对于时间差dt,如果$ ......

BZOJ1941 Hide and Seek

题目传送门 Solution: 可能是我写KDtree最后一道题了,主要是重新理解了KDtree点到块的距离在针对最大值和最小值的不同计算方式。 结合前面的两篇: 1、插入 2、求最大(小)点对 3、求k远点对 也只会这些操作了,可能还是我太菜。 Code: C++ #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n,m,ansmn,ansmx,opt,k1,k2,D,root,ans; struct node { int l,r,mn[2],mx[2],d[2]; }t[800010]; inline int read() { int ans=0, ......