BZOJ3295 动态逆序对(树套树)

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3295

对于每一次修改,我们只需要知道在x前面有几个数比它大,在它后面有几个数比它小,然后就可以维护逆序对的数量了。那么问题是怎么算出在x前面有几个比它小呢?可以用树套树,外层树状数组,内层线段树。外层树状数组维护位置为1~i的前缀和,内层线段树维护值在l~r的数有几个。然后就可以完美的解决问题了。这道题用bit套线段树代码非常短。

code:

3 条评论
  1. I not to mention my guys have been checking out the great information on your website and immediately got an awful suspicion I never expressed respect to you for those tips. All of the guys came absolutely passionate to learn them and have in effect actually been making the most of those things. Appreciate your genuinely very accommodating as well as for settling on this kind of marvelous areas millions of individuals are really desirous to understand about. My personal honest apologies for not expressing appreciation to you earlier.

  2. I am only commenting to make you understand of the amazing discovery my wife’s princess obtained browsing your webblog. She learned plenty of pieces, with the inclusion of how it is like to have an amazing giving nature to get other people with no trouble know just exactly specific extremely tough matters. You undoubtedly surpassed her expectations. Thanks for supplying these essential, dependable, explanatory and in addition easy guidance on the topic to Julie.

  3. I in addition to my guys have already been reading through the nice items on the website and the sudden I had an awful feeling I had not expressed respect to the web site owner for those techniques. The ladies happened to be absolutely excited to study all of them and already have truly been enjoying them. I appreciate you for turning out to be simply helpful and also for settling on certain cool tips millions of individuals are really eager to learn about. My personal honest apologies for not expressing appreciation to sooner.

发表一条评论