博客
分类
标签
归档
友链
关于
博客
分类
标签
归档
友链
关于
GoldenPotato137的小屋
[BZOJ 3744] Gty的妹子序列
题面 3744: Gty的妹子序列 Solution 这是一道分块妙题。 区间逆序对…log数据结构应该是没法搞的。 因此,我们考虑用分块解决这个问题。 设$f[i][j]$表示第$i$块与第$j$块的所有元素的逆序对个数 这个东西我们可以考虑用线段树/树状数组直接搞,我们把所有数字从大到小插入,(数字相同的时候一起插入),每插入一种数字,我们可以直接计算它到其他所有块会新产生的逆序对数:...
2019-03-20
主席树
分块
数据结构
线段树
主席树
分块
数据结构
线段树
阅读全文
[Luogu P3567] [POI2014]KUR-Couriers
题面 洛谷P3567 Solution 大水题啊,真没什么好讲的 我们考虑建一颗权值主席树,从左往右逐个插入。因为个数满足可减性,因此我们可以很方便的“扣”出$[L,R]$区间构成的主席树。接下来只需要在树上二分看一下有没有出现次数超过$K$的即可。 时间复杂度$O(nlogn)$ 就酱,这题就被我们切掉啦︿( ̄︶ ̄)︿ Solution 123456789101112131415161...
2019-03-07
主席树
数据结构
主席树
数据结构
阅读全文
[Luogu P3302] [SDOI2013]森林
题面 洛谷P3302 Solution 拿到这道题,我们不妨先想一下静态的树上K大怎么搞。 静态树上K大有两种办法,一是树链剖分+平衡树,二是主席树做链前缀和。前者的复杂度是$O(log^2n)$的,而后者只有$O(logn)$。 我们考虑把数字全部离散化,然后开权值主席树,每颗主席树记录从它出发到根的路上每个数字出现了多少个。接下来,我们只需要找到LCA。因为数字出现个数满足可减性,因此...
2019-03-07
主席树
数据结构
主席树
数据结构
阅读全文
[CF893F]Subtree Minimum Query
题面: 传送门:Codeforces 题目大意:给你一颗有根树,点有权值,问你每个节点的子树中距离其不超过k的点的权值的最小值。(边权均为1,强制在线) Solution 这题很有意思。 我们一般看到这种距离不超过k的题目,第一反应一般是建以深度为下标,以dfs序为时间轴的的主席树。 很不幸,区间最小值并不能通过减去历史状态得出某个子树的状态。 所以说,这题妙在思想的转换。 考虑以dfs序...
2019-02-22
主席树
数据结构
主席树
数据结构
阅读全文
[Luogu P3899] [湖南集训]谈笑风生
题面 传送门:洛谷 Solution 你们搞的这道题啊,excited! . 这题真的很有意思。 首先,我们可以先理解一下题面:固定一个a,找到一个b,c就是a与b的公共子树中的某个点。 那么,我们显然可以把这个b分成两类,第一种是在a上面的,第二种在a下面的。 对于b在a上面的情况,**显然,c一定是a的子树中的某个点,**答案即为$min(K,depth[a])*size[a]$ 对于...
2019-02-22
主席树
数据结构
主席树
数据结构
阅读全文