zcmimi's blog

categories/算法/离线/共5篇文章

avatar
zcmimi
2020-07-11 07:23:00

有一类普通莫队不可解的问题就是在转移区间过程中,可能出现删点或加点操作其中之一无法实现的问题,这时可以使用回滚莫队算法

avatar
zcmimi
2020-04-16 22:39:00

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

avatar
zcmimi
2020-03-25 17:13:00

整体二分是离线算法

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

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

以静态区间第k小为例,[LG P3834 【模板】可持久化线段树 1(主席树)](https://www.luogu.com.cn/pro

avatar
zcmimi
2020-03-20 20:36:00

二维偏序

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

例题: [SHOI2007]园丁的烦恼

离线操作

先将每个询问拆成4个点查询

(1,1)(x,y)中点数为s(x,y).

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

树上莫队:

也就是把莫队搬到树上

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

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

1/1
Search
search