zcmimi's blog

arrow_back线段树共44篇文章

avatar
zc
2020-04-25 16:51:00
查看原题

点击跳转

枚举右端点r,当前颜色x

lst_x为颜色x上一次出现的位置

假设我们已经得知了f(l,r-1),l\in [1,r-1]

那么f(l,r),l\in [lst_x+1,r]=f(l,r-1)+1

也就是说我们把[lst_x+1,r]区间+1就可以了

于是这题就变成了线段树(或树状数组)维护区间平方和

avatar
zc
2020-04-12 15:41:00
查看原题

点击跳转

1 x表示把点x到根节点的路径上所有的点染上一种没有用过的新颜色

从这里可以看出每种颜色在树上都是一条链的形式存在

可以发现这和LCT很像

那么1操作可以看成access操作,(如何操作先放着

x到根的颜色种数也就是要经过的虚边的条数,设为S_x

xy的路径的权值,可以使用树上差分的形式

也就是转化为S_x + S_y - 2\times S_{lca(x,y)} + 1

3操作也就是求子树最值

我们回过头来看access操作:

  1. 原来的实边变虚,意味着要多走一条虚边,将此链所管辖的区域全部+1

  2. 虚边变实边,意味着要多少一条虚边,将此链所管辖的区域全部-1

注意: LCTsplay的父子关系并不是原树中的父子关系,要找到该splay中深度最小的节点(也就是这条链的顶端再操作)

综上可以用 lct+lca+dfs序+线段树 解决

当然也可以通过树剖模拟access的形式来解决

avatar
zc
2020-03-28 23:23:00
查看原题

点击跳转

树套树解法

此题对树套树爱好者极不友好!

首先高高兴兴地写了个树状数组套动态开点权值线段树,发现MLE了,多次调整空间后发现要么re要么mle,难道只能用cdq分治或k-dtree了吗?

好不容易写完的代码舍不得随便删掉

既然卡空间,那我离散化坐标,再把树状数组也改成动态开点线段树还不行吗? 还真不行

我感到了这题深深的恶毒

只能动用黑科技了!

"线段树的压缩路径",如果没有询问要访问这个节点,那就不继续向下开点,以节约空间!

内层和外层都开,终于通过了这道恶毒的题

avatar
zc
2020-03-28 15:20:00
查看原题

点击跳转

树链剖分树套树

这里的树套树使用树状数组动态开点权值线段树实现,要先离散化

我的方法算是有点笨但是好写的方法

avatar
zc
2020-03-25 23:54:00
查看原题

点击跳转

树套树

外层权值线段树 内层区间修改线段树

内层线段树需使用标记永久化,否则可能TLE

外层可以使用非递归结构提高速度

可以预先离散化提高速度

avatar
zc
2020-03-24 09:05:00
查看原题

点击跳转

离线解法: cdq分治

将问题转化为三维偏序

我们先找出对答案有贡献的点(i,j)满足的条件:

time_i<time_j

val_i<val_j,pos_i>pos_jval_i>val_j,pos_i<pos_j

avatar
zc
2020-02-28 17:31:00
查看原题

点击跳转

可以想到贪心:

如果目前有可以摧毁的目标水晶,那么摧毁最靠后的

否则摧毁第一个水晶

证明:

如果一个水晶目前无法摧毁,它必须等前面若干个水晶被摧毁它才能移动到目标位置

所以当目标水晶没有可以摧毁的时候,摧毁序列第一个可以移动最多的目标水晶

当有超过一个目标水晶可以摧毁的时候,从后往前摧毁显然是最优的

那么要如何实现这个贪心呢?

很容易想到数据结构

  1. 平衡树暴力操作: 数据范围3\times 10^6,显然是不行的

  2. 线段树 目标水晶最多1.5\times 10^6,且线段树常数不大,可行

实现:

  1. 线段树维护

维护d_1,d_2,\dots,d_{cnt}表示目标水晶到可以摧毁的位置的距离

维护最小值

若最小值为0,这找到最靠后的d_x=0,摧毁,也就是距离赋值为无穷大,然后将d_i,i\in[x+1,cnt]都减去1

否则一直摧毁第一个水晶直到最小值为0,也就是所有d_i都减去min(d_i)

代码如下:

avatar
zc
2020-02-14 14:21:00
查看原题

点击跳转

对于第二问:

看到数据范围可以想到矩阵快速幂求斐波那契数列

矩阵乘法具有分配率: AC+BC=(A+B)C

我们可以想到用线段树维护矩阵区间乘

avatar
zc
2020-01-27 18:12:00
查看原题

点击跳转

建完广义圆方树后用树链剖分+线段树维护

修改一个点的时候,考虑到要修改它所在的双连通分量中的点,我们可以在(它的父亲)方点建一个对顶堆来维护最小值

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

动态开点线段树模板

2/5
Search
search