zcmimi's blog

arrow_back算法共22篇文章

avatar
zcmimi
2020-02-01

Dynamic Rankings为例:

如果不带修改,那就是普通的主席树

待修改: 树状数组套动态开点权值线段树

对于修改a_p,

受影响的有[p,n]

但是我们不需要从p修改到n

可以

avatar
zcmimi
2020-01-26

对于类似f_i=\min_{j=1}^{i-1}f_j+val(i,j)的方程

比如val(i,j)=a_i\times b_j,同时包含了i,j两个变量,

这样没法直接用单调队列

如果把val(i,j)展开能转化成$\frac{y{j1}-y{j2}}{x{j1}-x

avatar
zcmimi
2020-01-02

形态: 在一棵树上加多一条边

实现:

找出环后一次处理环上每个点的子树,然后再处理环

[IOI 2008]Island(求基环树直径)

IOI 2008 Island

先找出环,把环当根节点,找出每棵

kruskal重构树

我们回想一下kruskal生成最小生成树的过程:

先将边按边权从小到大排序,然后依次加入

如果x,y已经联通,则跳过这条边

否则连接x,y

kruskal重构树是在kruskal生成最小生成树的,

连接x,y时,将边权变成一个新的节点$

avatar
zcmimi
2019-11-11

静态链分治用于解决静态树上众数问题,比如Codeforces\ 600E

静态链分治是离线算法,有点像莫队,复杂度\Theta (n \log n \log n)

比如说遍历一遍子树可以得出答案,但是每棵子树

avatar
zcmimi
2019-11-01

点分治

点分治用于大规模处理树上路径

树的重心

树的最大子树最小的点

性质:每一个子树的大小都不超过\frac n2

```cpp int rt,mxs=inf,siz[N];// 当前 根,最大子树大小 void frt(int x,int f){ siz[x]=1

前置知识: 莫队算法(Mo's Algorithm)

树上莫队:

也就是把莫队搬到树上

入手模板: SP10707 COT2 - Count on a tree II

给定一个n个节点的树,每个

avatar
zcmimi
2019-01-21 11:31:55

转自https://www.cnblogs.com/hadilo/p/5914302.html

欧几里得

定义:

gcd(a,b)为整数ab的最大公约数

引理:

gcd(a,b)=gcd(b,a \bmod b)

证明:

设$r=a \b

avatar
zcmimi
2019-01-20 00:23:01

二维线段树一般用线段树套线段树写,当然也可以用四叉树

树套树,顾名思义,外层树的每个节点都是一棵树。

[题目地址:https://www.luogu.org/problemnew/

avatar
zcmimi
2018-12-29 22:31:53

学习的原因:

之所以选择fhqtreap,不是因为可以可持久化,是因为:

1. 短

2. 好理解、好记

3. 应用范围广

不过学之前还是先对treap原理稍微有些了解比较好

其中有些细节还是要靠自己意会意会

原理:

概述:

f

2/3
Search
search