zcmimi's blog

arrow_backcdq分治共4篇文章

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

点击跳转

树套树解法

此题对树套树爱好者极不友好!

首先高高兴兴地写了个树状数组套动态开点权值线段树,发现MLE了,多次调整空间后发现要么re要么mle,难道只能用cdq分治或k-dtree了吗?

好不容易写完的代码舍不得随便删掉

既然卡空间,那我离散化坐标,再把树状数组也改成动态开点线段树还不行吗? 还真不行

我感到了这题深深的恶毒

只能动用黑科技了!

"线段树的压缩路径",如果没有询问要访问这个节点,那就不继续向下开点,以节约空间!

内层和外层都开,终于通过了这道恶毒的题

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-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
查看原题

点击跳转

1/1
Search
search