zcmimi's blog

arrow_back树套树共4篇文章

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-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-25 23:54:00
查看原题

点击跳转

树套树

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

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

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

可以预先离散化提高速度

1/1
Search
search