忠诚 标签(空格分隔): 树状数组 线段树 题目描述 老管家是一个聪明能干的人。他为财主工作了整整10年,财主为了让自已账目更加清楚。要求管家每天记k次账,由于管家聪明能干,因而管家总是让财主十分满意。但是由于一些人的挑拨,财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚,他把每 …

题目大意 给一个森林,森林有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 …
HDU3016 Man Down

题目大意 大家一定玩过Mandown(参考图片)。人可以从每块板的左右两端垂直往下掉,落到一块板上能得到分数(可正可负),且中途不能变负(初始值100),问落到地板上的最大价值。 n<=100000 Solution 其实只要知道每块板往左和网友都会落到那块板,再从上到下做一次DP就可以。 但 …

题目传送门 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 意义下相等)发现他们相差 …