标签为 [线段树] 的文章

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。交上去后,喜闻乐 ......

HihoCoder1034毁灭者问题

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

BZOJ3545 Peaks

题目大意 在Bytemountains有N座山峰,每座山峰有他的高度h_i。有些山峰之间有双向道路相连,共M条路径,每条路径有一个困难值,这个值越大表示越难走,现在有Q组询问,每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰,如果无解输出-1。 N,Q<=100000 题解 对路径按困难值排序 对询问按x排序 然后可以用平衡树合并也可以线段树合并 所以当然是写简单易懂的线段树合并啦 我们要来膜拜一下hjq大佬 代码 C++ #include <cstdio> #include <algorithm> str ......

BZOJ2141 排队

题目传送门 Solution: 这就是一个裸的动态逆序对问题,对于每一次交换,可以看作是先删掉一个数,再删一个数,然后加入一个数,再加入一个数,所以只要解决插入和删除就可以了。对于删除,我们只需要知道在x前面有几个数比它大,在它后面有几个数比它小。对于插入,我们也只需要知道在x前面有几个数比它大,在它后面有几个数比它小。然后就可以维护逆序对的数量了。这个可以用树套树来完成,外层树状数组表示位置为1~i的前缀和,内层线段树表示权值在l~r的数的个数。 code: #include&lt;cstd ......

BZOJ4785 树状数组

题目传送门 solution 写错的树状数组其实就是求一个后缀和,设suml[i]为前缀和,sumr[i]为后缀和,则题目要求suml[r]-suml[l-1],然后我们来比较一下suml[r]-sum[l-1]和-(sumr[l-1]-sumr[r])(相反数在mod 2 意义下相等)发现他们相差的就是val[l-1]和val[r],然后要使他们相等就是说val[l-1]和val[r]要在mod 2意义下相等,当l=1时就是询问一个点的前缀和和后缀和是否相等。 然后将每个询问看成一个二维平面上的点,(l-1,r),用树套树来维护点合法的概率,用(l1,r1,l2,r2)表示左端点在l1,r1间,右端点在(l2,r2)间的所有区间,然后在(l,r ......

BZOJ3295 动态逆序对(树套树)

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3295 对于每一次修改,我们只需要知道在x前面有几个数比它大,在它后面有几个数比它小,然后就可以维护逆序对的数量了。那么问题是怎么算出在x前面有几个比它小呢?可以用树套树,外层树状数组,内层线段树。外层树状数组维护位置为1~i的前缀和,内层线段树维护值在l~r的数有几个。然后就可以完美的解决问题了。这道题用bit套线段树代码非常短。 code: #include&lt;cstdio&gt; #include&lt;algorithm&gt; #include& ......

BZOJ2212Tree Rotations(线段树合并)

题目大意 有一棵2n-1个节点的二叉树,每个叶子节点上有一个权值(1..n的排列)。可以任意次交换某两棵兄弟子树。问最后叶子上的权值按先序遍历排序后逆序对的最小对数。n<=200000(参考图片) solution 因为两棵兄弟子树换或不换,对它们的祖先和儿子是没有影响的。所以从下到上搜索,并判断这个节点的两棵子树是否交换。考虑贪心,如果交换后能减少两棵子树之间形成的逆序对,就可以交换它们。 而怎么计算两棵子树交换后逆序对的变化情况?只要算出交换前两棵子树之间的逆序对个数就可以了。这用什么来维护呢? 如果用平衡树 ......

HDU1828 Picture

题目大意 给定n个矩形(边平行于坐标轴),求被矩形覆盖图形的周长。 Solution 我们可以分别统计与x轴,y轴平行的周长之和。计算每条线段对答案的贡献。如果这条线段的某几段在被覆盖的图形外面,就可以加入答案。 例如对于平行于y轴的线段。用扫描线的方法,从左往右依次扫描,扫到左边的一条线段时,把整个区间整体+1,扫到右边的线段时,把整个区间整体-1。而操作时值是否为零发生变化的点,就是这条线段在被覆盖图形外面的点,也就是这条线段对答案的贡献。用线段树维护就可以。由于加上和减去的区间是一样的,甚至不用在修改 ......