menu zcmimi's blog

arrow_back 树状数组

有多种做法

AC自动机暴力

AC自动机+树状数组+lca+dfs序

后缀数组+ST表+树状数组

AC自动机暴力

原数据可以过,后来添加了加强数据就tle了

对点名串建立AC自动机

zc
2020-05-17 16:09

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

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

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

那么$f(l,r),l\in [lst_x+1,

zc
2020-04-25 16:51

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

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

可以发现这和LCT很像

那么1操作可以看成access操作

zc
2020-04-12 15:41

\sum_{i=l}^r deep[LCA(i,z)]

首先,可以把询问拆成两个部分相减$\sum{i=1}^r deep[LCA(i,z)]-\sum{i=1}^{l-1} deep[L

zc
2020-04-05 22:51

树套树解法

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

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

zc
2020-03-28 23:23

树链剖分树套树

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

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

```cpp

include<bit

zc
2020-03-28 15:20

整体二分

接近模板题 ```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il
zc
2020-03-26 01:21

离线解法: cdq分治

将问题转化为三维偏序

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

time_i<time_j

val_i<val_j,pos_i>pos_j或$val

zc
2020-03-24 09:05

二维数点模板 ```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il __in
zc
2020-03-23 17:38

先离散化,然后用树状数组统计两边的数目,比较即可 ```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
zc
2020-03-23 00:30
1 / 3
Search
search