OceanEye's Blog

是时候表演真正的技术了!

@OceanEye2月前

06/15
21:12
OI

BZOJ2243

树链剖分
细节打错了然后wa了好久

数据

BZOJ2243

@OceanEye3月前

06/4
13:26
OI

BZOJ4034

简单的树链剖分,分轻重链之后依然满足DFS序的性质所以可以用线段树的区间加来表示子树加法

挂代码

BZOJ4034

@OceanEye3月前

05/19
16:03
OI

BZOJ4869

这道题是这样子的……一个区间求和一个区间加幂

之前刚刚学了降幂大法就是为了写这道题:-D

然后就直接肝……当然最后还要展开多一层的1[EXM?]

 

BZOJ4869

@OceanEye4月前

04/12
23:33
OI

BZOJ4299 CodeChef FRBSUM

很强的题目= =超级烦

想来想去想不懂怎么写

一个很朴素的想法就是排序然后一个一个加进去

假设当前已经满足可以取[0,P]之间的取值

新进来一个数q

如果q在[0,P+1]之间的话就可以拓展 P -> P+q

否则停止拓展,因为显然后面那一堆都不满足要求

然后我就不会了= =跑去翻了翻题解  [传送门]

发现可以连着处理一段的sum,时间复杂度大致是单次log方的。

真神奇

 

BZOJ4299 CodeChef FRBSUM

@OceanEye4月前

04/8
18:51
OI

POJ 2777 线段树+bitset

妈呀这题真卡时。
不得不承认这是我第二道用递归线段树AC的题目qwq太感动了
这题差不多是线段树的裸题了,,只需要bitset维护每一条线段上的颜色还有记得维护PushDown标记就好了。
其他都是细节问题,但是不知道为什么我加了读入优化之后就爆炸WA,,
所以只贴一份AC的无读入优化的代码好了qwq

 

POJ 2777 线段树+bitset

@OceanEye4月前

04/8
18:43
OI

51nod 1681 主席树

这题主席树的处理还是有点神的,,
maya我直接抄题解就好了,,反正我方法的和题解是一样的。
但是我比好多人都慢啊QAQ不服气

首先转化问题。两棵树的公共祖先,很扯淡。计算出每两个点的两棵树上的公共祖先我用的复杂度是n^2·logn
妈呀根本不能接受,妥妥的TLE
那么我们计算祖先的贡献怎么样?
首先假设某个点有x个公共儿子,那么他对总的亲密度的贡献是x*(x-1)/2【自己脑补组合数】
但是看一眼数据范围,首先O(n)应该是不可能的了。那么我们能不能在nlogn的时间内瞎搞出所有节点的公共儿子呢qwq
平衡树?搞毛,,线段树?搞毛,,树剖?不好意思不会,,主席树?于是又神奇的想到了转化问题

他的标号是混乱的,这很不清真,,换成DFS序怎么样?
第二棵树呢?还是混乱的,,

混乱又怎么样,,再标一次就好了。这个时候我们要的就是完成两个集合求交集的工作。
那么主席树出场了!

第一棵树的节点先按照dfs序重新编号,记节点A的子节点为l到r
然后第二棵树也这么做,,记节点A的子节点为L到R
这个时候,会惊奇发现他们的公共儿子【交集】不就是求[L,R]中有多少个元素属于[l,r]的么,,
由于这个东西目测满足区间加法,所以主席树应该是可行的。
那么就主席树瞎搞一下,,A掉。
爽!

51nod 1681 主席树