zcmimi's blog

arrow_back离散化共5篇文章

avatar
zc
2020-10-29 10:15:24

查看原题

点击跳转

答案与位置没有关系,把序列当作集合来看

设大于等于s的数有cnt个,小于s的数和为sum

那么sum\ge s(c-cnt)

可以用 离散化+树状数组 / 平衡树 维护

avatar
zc
2020-03-01 19:36:00
查看原题

点击跳转

先离散化权值为排名,从大到小排序

遍历所有点,用权值树状数组统计,结果是 遍历完该子树后答案 - 遍历该子树前答案

(为什么一开始会去想什么dsu on tree和线段树合并

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

可以先看一下LG P4868 Preprefix sum,很经典一道题,维护一下后缀和就可以了

这题的话就是把上面那道题变了一下

由于值域太大,我们可以使用 动态开点线段树 或 树状数组+离散化

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

点击跳转

解法1

主席树+离散化(深度太大需要离散化)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先把血统编号离散化

两个点之前最多只能有k种血统的牛,所以我们考虑使用two\ pointers

O(n)

1/1
Search
search