zcmimi's blog

arrow_back数据结构共19篇文章

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

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

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

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

avatar
zcmimi
2019-01-20 00:22:39
avatar
zcmimi
2018-12-29 22:31:53

学习的原因:

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

1. 短

2. 好理解、好记

3. 应用范围广

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

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

原理:

概述:

f

avatar
zcmimi
2018-12-01 21:10:58

https://www.luogu.org/problemnew/show/P3369

最短(最简洁)代码:

解释:
turn(x,p):
    将x的左(p=0)/右(p=1)儿子旋转到x的头顶(变成x的父亲)

![](https://i.loli.net/2018/12/05/

avatar
zc
2020-03-27 20:17:00
查看原题

点击跳转

此题非常之毒瘤,我写的整个人都二逼了

共有一下几种解法:

  1. 树状数组套线段树
  2. 线段树套平衡树
  3. 权值线段树套平衡树
  4. 分块
  5. 整体二分

树状数组套线段树

离散化+树状数组套动态开点线段树

这应该是一种常数小又好写的方法了,不开o2也轻松过

可以参照LG 2617 Dynamic Rankings的做法

简要说下思路:

树状数组记录位置,权值线段树记录权值

树状数组的每个节点都是一颗权值线段树

  1. 查询区间内一个数的排名:

    在树状数组上找到区间对应的节点,对应的权值线段树线段树树内查询对应数的排名并求和。

  2. 查询区间内排名为k的数是几:

    找出树状数组中所有对应节点,然后权值线段树上二分(与主席树的方法相似)

  3. 单点修改:

    相当于树状数组上的单点修改,在对应节点的权值线段树中删除原数,加入新数

  4. 前驱:

    查询排名,然后找排名-1的数

  5. 后继:

    查询排名,然后找排名+1的数

语文不好,不大会表述,相信数据结构这种东西直接看代码更好理解

具体可以看代码

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

点击跳转

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

点击跳转

允许离线处理

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

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

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

x_i+y_i-\max(x_j+y_j)

坐标再旋转并处理三次就可以了

avatar
zc
2020-03-20 21:22:00
查看原题

点击跳转

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

这个图是个DAG,我们可以很快地处理出每个点以他为起点(ds_i)或终点(dt_i)的最长路

接着我们枚举删掉哪个点

我们可以将拓扑序小于当前点的点称作A集合,大于的称作B集合

删掉这个点后的最长路有三种可能:

A\rightarrow A,A\rightarrow B,B\rightarrow B

(to指x连接的点)

当删除一个点x时,我们可以删去所有集合中的dt_to+1+ds_x(反向图中的)

求出集合中的最大值就是当前最长路长度

接着将dt_x+1+ds_to加入集合,转移到下一个状态(原图中的)

于是我们需要一个数据结构满足以下要求:

  1. 插入某个值
  2. 删除某个值
  3. 查找最大值

我们可以用堆(手写堆或者两个stl优先队列)、平衡树、权值线段树等维护

2/2
Search
search