ds

一点闲话 感觉这题好弱啊.应该有一堆神犇能秒吧. 取模是为了避免输出long long的问题.不知道有没有人中间就取模了2333. 这题的idea源于wc2015的k小割.考场上写了良久最后mle. 于是我决定这题既不卡空间也不卡时间. 是不是感觉我的题比ioi和zyf的题都良心啊hhh 测试点1-6 这六个点的权值和非常小.于是可以树形dp.用fi,j表示以i为根的子树中权值和为j的方案总数.于是可以dp一下就得到答案. 测试点7-8 接下来的点都是大数据了,然而还是有一些部分分. 比如这个. 没有题的一条链情况比这个题更简单了吧ovo 测试点9-10 这是最简单的菊花图ovo似乎就是k小割的弱化版啊.做法比较多喽. 介绍一个叫做学姐二分的方法.二分一个答案,然后强行dfs方案.如果总方案数大于k就直接结束.这样是可以保证复杂度的TAT 测试点11-12 一条链变成两条链了.一样的二分答案然后枚举一边二分另一边嘛. 剩下的测试点 这些点没办法用奇怪的方法了吧?有人用奇怪方法黑过去的和我说一声ovo 考虑当前如果已选的某个点集S,我们也把它叫做一个状态. S可以向S中任意点的没有在S中的儿子扩展.设扩展后的状态叫S’.(它可能有很多个) 不难想到,已知前k小的状态S1 .. Sk后,第k+1小的状态一定是S’1 .. S’k中权值和最小的一个. 于是我们就是要维护当前所有状态的可扩展的状态. 对于每一个状态,用一个可持久化堆来记录它能扩展到的所有点,然后取其中最小的一个加上它本身的权值和扔进外层的堆里. 那么每次外层堆里的最小值就是第k+1小的状态. 那么找到k+1小状态后,就要将这条边从原状态中删除.然后对于新扩展出来的状态,把新扩展出来的原树上的点的所有儿子也扔到这个状态的堆里就好了.注意有的点的度数会很大,所以每个点的儿子本身就要用可合并堆来存. 然后直接找下去直到扩展出第k小的状态就行了. 以上所有操作的时间复杂度都是O(log(n))的,所以总复杂度是O(k*log(n))的. 另一种思路 上面提到过的"学姐二分"也可以应用到这里.因为我也没写过所以不作重点介绍了.大家可以自行思考一下. 劼司机的思路 (苣蒻的出题人并不能理解这种做法,你可以去找劼司机本人讨论ovo) 就是把树画到平面上。。 然后建个对偶图 对偶图里每条边的边权为他子树里边权和 也就是。。 在对偶图里走过一条边，等于把这条边下面的子树砍掉。。 然后就没了。。。 吉利就是这么虐人的！ 松爷好强!

rausen大爷太强辣! 嗯看到这个东西,咦,直线某一边的点的权值和?kd-tree上上上. 于是就开敲kd-tree.敲到一半弃emacs换vim. 然后就wa了.然后发现double的精度太高了ovoovo 于是rausen跑得好快啊.

之前感觉是sg函数.不过不会.在wulala神犇的指点下找来题解看了一下.太神辣.自己肯定想不出来… 设以点u为根的子树的局面的sg值为sgu.设以u为根的子树中先手先hack掉v后的sg函数为gu,v. 那么gu,v = f[v] xor ∑ fu到v路径上所有点的非主干儿子. 然后fu = mex{gu,v} 这个转移得转移是O(n2)的样子吧. 然后发现某棵子树的g其实每次都是异或了一个相同的值.而且会合并. 咦可以用trie来优化一下.打下标记啥的.然后根据主席的论文这个东西是O(log n)的?虽然感觉复杂度证明没有说清楚啊ovoovo 然后就在trie树标记上卡了好久啊火冒三丈ing

mhy写此题写了良久啊然后T啊T,T啊T.然后我去翻了一下seter的博客.结合他的东西yy出一种比较优越的做法. 如果我是出数据的,我会出两种数据,菊花图和链. 如果是菊花图,直接朴素ovoovo如果是链,可以以每个叶子节点为根建一次可持久化线段树. 如果是链上长出了一团菊花… how to 结合? 不停地删叶子.如果删到某层时叶子足够少了,那就建可持久化线段树去. 对于询问,有若干种情况. 标记每个根里离得很近的点. 如果两个中有一个被标记过,那么直接以这个根求另一个的答案,然后朴素查找近的这个点到根的答案. 如果两个点都没有被删 ,那一定有至少一个根可以使得这条链的两个端点有祖先关系.这样的话直接用可持久化线段树求解. 好像完了?然后wa了ovoovo 还有一种情况是某个点被删了,但是删之后它是接在树枝上的! 于是它离根很远,还不一定有能搞出祖先关系的解. 于是先爬行到没被删的地方,看两个端点是否在同一棵被删的叶子树上. 如果是就朴素了. 如果不是的话,先求没被删的这一段,再朴素被删的一段. 终于完辣. 从来没写过这种代码.感觉自己萌萌哒.

最近都在做梦的感觉啊.这道题倒是mhy的博客一语点醒梦中人. 只会加正数,所以每个数只有至多一次会从负变非负. 链剖是肯定的.然后记录一下当前最大的负数是谁.如果大于等于0就改掉.所以还是O(n*log2n). 所以我还是太弱了.于是读入优化大法抢了一个rank1.

bc fst爽翻.然后这题差二十分钟没调出来不然我就是rank1.还是应该直接敲而不是去和队友商量. 静态做的话直接按位树分就好了.然后资瓷修改的时候也是一样.只是把之前求的信息在树分后的dfs序上用线段树记下来.也就是要随时知道某个分治层里的某个子树上有多少个0或者1. 然后就是讨论某个修改对当前答案的贡献.要注意分治根的值,以及有贡献的是哪些位置.中间打错了外层的dfs序范围,导致调试了很久.明明想清楚了但是打错了,不应该的. 只有完了之后交了然后怒虐标程好开心啊.

其实是一道没多大意思思的码农题TT然而这是我的第800题所以要mark一下. gcd序列可以用插分序列+第一个数来支持区间加.二维那就二维差分喽. 然后发现第一个数似乎没有办法维护啊.不能做了?! 询问的方式比较奇怪,有一个中心.那就建4个方向吧.这样似乎可做了yeah. 所以我还是太naive了啊. 是时候屯一波题了.

业界毒瘤ioi开的坑.然后被强行看了一下于教授的代码.然后觉得也不太难嘛. 看了一下条件.只和同行或者同列有关?那就拿map套动态建树的线段树好了辣. 然后距离是欧式距离?那就把完全平方式展开,发现只需要在线段树里记录一下个数,和,平方和,搞定了辣! 然后alloc的时候–写成了++,查错良久,囧.

最近整个人都被Sone1搞得头昏脑胀。不爽ing。 这个题其实就是线段树+维护的题。考虑给一个区间里每个数加C的时候的式子会变成什么样就好了。 然后要注意标记得随时下传，不能永久化。 然后感觉时间有点慢不过跑起来还将就。 然后我太弱了。

这是apio里我最自豪的一道题了.让三分党去…吧. k=1直接在所有坐标的中位数处建桥就行了不要问我为什么. 首先感受一下发现可以按(a+b)把序列分成两半,然后两半就是k=1的情况嘛.那直接处理一下每个前缀和后缀的答案就完了辣.