zcmimi's blog
avatar
zc
2020-04-02 09:12:00
查看原题

点击跳转

容易看出x,y切断后,x的子树大小乘上y的子树大小就是答案

LCT维护子树大小即可

avatar
zc
2020-04-01 23:48:00
查看原题

点击跳转

按边权从小到大排序后,依次添加边

问题转化为了:

每次加边的时候,

如果两点为连通,则加边

否则在目前的生成树上找到边权最小的边, 并替换为新边

可以用LCT维护

avatar
zc
2020-04-01 19:37:00
查看原题

点击跳转

经典的link-cut tree维护连通分量

首先看到这种题我们可以考虑倒序添加

假设每个点代表一个双连通分量,那么两个点之间的关键路径数就是链长-1

可以用LCT+并查集来维护

连接一条边:

  1. 两端在同一个双连通分量中: 什么都不用干

  2. 两端还未连通: 直接link

  3. 两端已经联通: 缩点

    将连接两端的路径提取出来,合并这些点

avatar
zc
2020-03-31 22:37:00
查看原题

点击跳转

avatar
zc
2020-03-29 10:46:00
查看原题

点击跳转

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-26 01:21:00
查看原题

点击跳转

整体二分

接近模板题

avatar
zc
2020-03-25 23:54:00
查看原题

点击跳转

树套树

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

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

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

可以预先离散化提高速度

23/73
Search
search