标签 数据结构 下的文章:

4923: K小值查询 splay
发表于: | 分类:Oi | 评论:0 | 阅读:189
辣鸡bz卡我常数毁我青春 考虑把$>k$的数字分成两个部分,一部分在$[k+1,2k]$内,一部分在$[2k+1,inf]$ 在$[k+1,2k]$内的数字显然都至少变小了一半,那么每个数字最多在$log$次就变成了1,所以我们对于这部分直接暴力重新插入 然...

阅读全文>>

BZOJ 4127: Abs 树链剖分 线段树
发表于: | 分类:Oi | 评论:0 | 阅读:166
最近主攻tc已经快一周没写数据结构了qwq,写的脑袋疼然后回BZ找几道傻题写写 直接考虑序列这玩意咋做就行了剩下的就是强行套树剖 因为加的数字都是正的。考虑在修改的时候如果当前区间的负数的最大值+要加的数字>0就递归左右区间修改,否则直接打标记,分正负讨论即...

阅读全文>>

BZOJ 4644: 经典傻逼题 线性基 线段树
发表于: | 分类:Oi | 评论:0 | 阅读:199
经典傻*题 我刚开始的时候以为所选的点必须是连在一起的然后就YY了一个无向图最大割,后来发现根本不对,然后再看一遍题发现和割其实一点关系都没有233333333 我们把一个点的点权设置成连在他身上的所有边的边权的异或,那么显然这个东西求的其实就是最大异或和,如果一...

阅读全文>>

4025: 二分图 LCT维护动态二分图
发表于: | 分类:Oi | 评论:0 | 阅读:182
昨天半夜写来着,写完splay最后的讨论已经神志不清了 [早上一看写的什么玩意……删了重来 和以前我写的一道HDU的题目相似,这类题目都有两种解法,第一种是分治并查集,第二种是Lct,原理都是二分图中没有奇环 分治并查集的做法是建立一棵时间线段树,一个东西相当于一...

阅读全文>>

4771: 七彩树 主席树 DFS序
发表于: | 分类:Oi | 评论:0 | 阅读:182
非常神的一道题,和宋爷一起撕烤了很久才知道怎么做的…… 首先考虑怎么算贡献,最开始的时候我们可以吧所有点的点权设置成1,然后对于DFS序上两个颜色相同的点我们在他俩$Lca$身上标个-1就行了 注意是DFS序上连续的,这里连续的定义为中间没有和他颜色相同的点 这样...

阅读全文>>

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP