zcmimi's blog

arrow_back树状数组共33篇文章

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

点击跳转

整体二分

接近模板题

avatar
zc
2020-03-24 09:05:00
查看原题

点击跳转

离线解法: cdq分治

将问题转化为三维偏序

我们先找出对答案有贡献的点(i,j)满足的条件:

time_i<time_j

val_i<val_j,pos_i>pos_jval_i>val_j,pos_i<pos_j

avatar
zc
2020-03-23 17:38:00
查看原题

点击跳转

二维数点模板

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

点击跳转

先离散化,然后用树状数组统计两边的数目,比较即可

avatar
zc
2020-03-22 23:49:00
查看原题

点击跳转

首先可以想到按v_i排序

接下来就直接按顺序插入并统计就可以了

关于距离之和的统计:

可以分前半部分和后半部分统计

用树状数组维护即可

感觉很水

具体看代码吧

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

点击跳转

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

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

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

avatar
zc
2020-02-16 15:21:00
查看原题

点击跳转

f(i,k)表示前i位置,操作k次,最多剩下多少玉米

每一次的拔高操作区间右端点一定是最右边的玉米

f(i,k)=max_{j<i}(f(j,k-t))+1,a_i+t\ge a_j

直接枚举\mathcal{O(n^2k^2)}会超时,我们得想个办法优化

可以考虑用二维树状数组优化

优化为只需要两个树状数组

https://guodonglovesoi.blog.luogu.org/scoi2014-fang-bo-bo-di-yu-mi-tian

avatar
zc
2020-02-02 17:36:00
查看原题

点击跳转

AC自动机建完fail树之后子树的siz就是里面相同字符串的个数

每个询问可以拆成r的前缀和-l的前缀和

然后离线处理后用树状数组维护就可以了

主席树在线也可以

2/4
Search
search