menu zcmimi's blog

arrow_back 离线

先了解[WC2011]最大XOR和路径的做法

线段树分治+并查集+线性基

加边删边可以用按秩合并的并查集解决

zc
2020-06-04 19:43

核心思想: 把一个修改看成一个区间,每个询问是一个叶子,修改在线段树上打标记

zcmimi
2020-04-16 22:39

\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

整体二分是离线算法

顾名思义就是将所有答案一起二分

solve(l,r,st,ed)表示答案在[l,r],解决第sted个询问或操作

以静态区间第k小为例,[LG P383

zcmimi
2020-03-25 17:13

离线解法: cdq分治

将问题转化为三维偏序

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

time_i<time_j

val_i<val_j,pos_i>pos_j或$val

zc
2020-03-24 09:05

允许离线处理

可以看成三维偏序(坐标和时间)

考虑如果要求的点都在当前点的左上方

那么也就是要求x_j\le x_i,y_j\le y_i,time_j\le time_i

$xi+y

zc
2020-03-21 23:31

二维偏序

先按 第一维 排序, 第二维 用数据结构维护

例题: [SHOI2007]园丁的烦恼

离线

zcmimi
2020-03-20 20:36

AC自动机建完fail树之后子树的siz就是里面相同字符串的个数

每个询问可以拆成r的前缀和-l的前缀和

然后离线处理后用树状数组维护就可以了

主席树在线也可以 ```cpp

incl

zc
2020-02-02 17:36

自己写了个莫队,结果51nod跑的太慢,然后TLE(MLE)

题解妙极了:

离线之后,从左向右扫一遍,让每个值存储“当前已扫过的部分中,右边第一个与自己相等的点到自己的距离”,然后如

zc
2019-12-21 19:47

离线处理,倒着添加

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il 
zc
2019-12-21 19:47
1 / 1
Search
search