题目大意 给一个森林,森林有n个节点m条边。 现在有两种操作: Q x y k 表示询问x-y这条链上点权的第k小。保证x,y在同一个连通块里。 L x y 表示链接x,y两点。保证x,y在不同的连通块里。 总共有T次操作,要求强制在线,last表示上一次的答案,每次x,y,k都要异或last.la …

题目大意 有n个数,每个数一种颜色。m次询问,每次询问l,r区间内除去只有一个数的颜色的不同颜色的种数。 n,m<=1000,000 Solution 刚看到题目,就想到了一种非常方便的莫队做法。看了一眼数据范围,发现要$10^9$的复杂度,卡一卡就过去了。 我会函数式线段树,于是有口胡了一个 …

题目大意 假设你拥有 n 个魔法单位,他们从左到有站在一行,编号从 1 到 n。 每个单位拥有三项属性: si: 初始法力。 mi: 最大法力上限。 ri: 每秒中法力回复速度。 现在你操纵一个毁灭者,有 m 个操作,t l r,表示时刻 t,毁灭者对所有编号从 l 到 r 的单位,使用了魔法吸收。 …
BZOJ3545 Peaks

题目大意 在Bytemountains有N座山峰,每座山峰有他的高度h_i。有些山峰之间有双向道路相连,共M条路径,每条路径有一个困难值,这个值越大表示越难走,现在有Q组询问,每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰,如果无解输出-1。 N,Q<=1000 …

题目传送门 Solution: 这就是一个裸的动态逆序对问题,对于每一次交换,可以看作是先删掉一个数,再删一个数,然后加入一个数,再加入一个数,所以只要解决插入和删除就可以了。对于删除,我们只需要知道在x前面有几个数比它大,在它后面有几个数比它小。对于插入,我们也只需要知道在x前面有几个数比它大,在 …

题目传送门 solution 写错的树状数组其实就是求一个后缀和,设suml[i]为前缀和,sumr[i]为后缀和,则题目要求suml[r]-suml[l-1],然后我们来比较一下suml[r]-sum[l-1]和-(sumr[l-1]-sumr[r])(相反数在mod 2 意义下相等)发现他们相差 …

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3295 对于每一次修改,我们只需要知道在x前面有几个数比它大,在它后面有几个数比它小,然后就可以维护逆序对的数量了。那么问题是怎么算出在x前面有几个比它小呢?可以用树套树,外层树状数组,内层 …
BZOJ2212Tree Rotations(线段树合并)

题目大意 有一棵2n-1个节点的二叉树,每个叶子节点上有一个权值(1..n的排列)。可以任意次交换某两棵兄弟子树。问最后叶子上的权值按先序遍历排序后逆序对的最小对数。n<=200000(参考图片) solution 因为两棵兄弟子树换或不换,对它们的祖先和儿子是没有影响的。所以从下到上搜索,并 …

题目大意 给定n个矩形(边平行于坐标轴),求被矩形覆盖图形的周长。 Solution 我们可以分别统计与x轴,y轴平行的周长之和。计算每条线段对答案的贡献。如果这条线段的某几段在被覆盖的图形外面,就可以加入答案。 例如对于平行于y轴的线段。用扫描线的方法,从左往右依次扫描,扫到左边的一条线段时,把整 …