OceanEye's Blog

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

@OceanEye1月前

07/11
15:00
OI

NOIP2013货物运输

为什么我在写这题的题解……
因为这题我本来想用树剖搞过去的……结果炸了
:-D然后就写了现在的倍增

NOIP2013货物运输

@OceanEye2月前

06/15
21:12
OI

BZOJ2243

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

数据

BZOJ2243

@OceanEye3月前

06/4
13:26
OI

BZOJ4034

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

挂代码

BZOJ4034

@OceanEye3月前

05/7
22:56
OI

BZOJ2434

AC自动机的好题,充分利用了fail树的性质

性质:S串中每个包含了T的后缀的fail指针一定经过若干层指向T

fail指针不成环

把fail树上的点dfs重标号

处理单个询问时可以把S串中的每个节点的DFS序丢进树状数组里面

查询T对应节点的DFS区间即可

处理许多询问的话离线处理即可

为了保证在树上不跑 \(x^2\) 次

可以模拟之前插入节点的方式来计算……

当然开个vector在节点上记录id也是可行的……

代码应该很好看懂

[但是我写的代码一般都巨长所以没多少人看哈哈哈]

 

BZOJ2434

@OceanEye4月前

05/3
19:03
OI

BZOJ4012

某码农题
动态点分治[或者说点分树?]
转化一下[差分一下]就可以看出
要维护一棵树
可以在log~log方的时间复杂度内跑完整棵树的前缀和[1,l-1],[1,r]
于是用了点分树
树链剖分可不可以还没想过,目测是不行的
用了vector来控制空间
当然有大佬愿意写动态开点线段树或者平衡树也是很强的orz

BZOJ4012