题目大意 从一个序列中,找出k段连续的子序列,且每个子序列的长度不小于L,不大于R。 一个序列的权值定义为序列中所有数的和,求k个子序列和的最大值。具体看原题。 Solution 这道题应该用主席树来做,但是太麻烦。相比起来,ST表+堆的算法显然比较方便(可能我代码写得太丑)。 考虑每次取出一段最大 …

1.按秩合并的操作 相信大家都知道并查集(不相交集合森林),由于路径压缩优化后时间复杂度分析极难,不易理解,本文来讨论下一种易于分析的优化方式:按秩合并。按秩合并的时间复杂度是O(lgn)的,常数很小,虽然不是特别优秀,但在许多情况下也够用了。 按秩合并的方式就是,对于每一个结点x记录下一个秩(x. …

题目大意 给一个森林,森林有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$的复杂度,卡一卡就过去了。 我会函数式线段树,于是有口胡了一个 …

题目传送门 大概看了一下题目一脸懵逼,后缀数组?怎么维护修改、插入??仔细看题目好像不是这样的。。。用splay维护字符串,同时维护hash值,然后询问时只要二分+hash判定就好了。时间复杂度O(n lg² n)。主要是代码细节比较多,还有卡常。。。 code #include<cstdio …

题目传送门 n个点,n-1条边而且没有环,所以这是一棵有根树。看到要修改连边,以为是Link-Cut tree,可是又要子树修改和链查询。。。好像行不通。由于这是一棵根节点固定的有根树,考虑DFS序。记录每一个点u的入栈时间戳in[u]和出栈时间戳out[u],任意一个在以u为根的子树中的节点v,都 …
BZOJ1015 [JSOI2008]星球大战starwar

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

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

题目传送门 Solution: 可能是我写KDtree最后一道题了,主要是重新理解了KDtree点到块的距离在针对最大值和最小值的不同计算方式。 结合前面的两篇: 1、插入 2、求最大(小)点对 3、求k远点对 也只会这些操作了,可能还是我太菜。 Code: #include<cstdio …