【BZOJ 4358】permu

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4358
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/5049090.html
神犇题解Ⅱ:http://www.cnblogs.com/czllgzmzl/p/5644724.html

解题报告

1. 莫队+并查集

首先我们考虑一个简化版本:搞一个莫队,然后搞一个值域线段树
这样的话,我们的复杂度就是 $O({n^{1.5}}logn)$ 的,虽然可能会T,但很好想
现在考虑怎么把$log$去掉:如果莫队那里只存在插入操作,那么我们就可以使用并查集来维护
于是考虑莫队那里只有左端点的移动那里会有删除操作,于是我们每一次把左端点块内那一部分拿出来暴力重构
这样的话,复杂度就神奇地少了一个$log$!总复杂度: $O(n\sqrt n \alpha (n))$ 感觉可以A地样子!

2. KD-Tree

这里就是本题的高能部分!简直是太神啦!_(:з」∠)_
考虑将询问化为二维上的点,然后我们按照点值的大小,将序列的位置一个一个插入
每一次把所有包含他的询问的计数器加一,其他的询问的计数器置零
于是我们的每个询问对应的点上的计数器的历史最大值就是这个询问的答案啦!
时间复杂度:$O(n \sqrt n)$

14 thoughts to “【BZOJ 4358】permu”

  1. 423911 173738The vacation delivers on offer are : believed a selection of some with the most selected and in addition budget-friendly global. Any of these lodgings tend to be quite used along units may possibly accented by means of pretty shoreline supplying crystal-clear turbulent waters, concurrent with the Ocean. hotels packages 414657

  2. 534112 446086This internet site is truly a walk-through it genuinely may be the information you desired relating to this and didnt know who ought to. Glimpse here, and you will undoubtedly discover it. 555182

  3. 248405 735062This article contains wonderful original thinking. The informational content material here proves that items arent so black and white. I feel smarter from just reading this. 132069

  4. I am now not positive the place you are getting your information, but good topic. I must spend some time studying more or working out more. Thank you for fantastic info I used to be looking for this info for my mission.

发表评论

电子邮件地址不会被公开。 必填项已用*标注