codeforces 220 E. Little Elephant and Inversions (树状数组+尺取)

题目链接

题意:

how many pairs of integers l and r are there, such that 1 ≤ l < rn and sequence b = a1a2alarar + 1an has no more than k inversions.

我花了两个小时才看懂题。。。。一直没懂b数列中a[l]和a[r]怎么就挨着了。。。

其实意思是。。。只保留a数列中1..l和r..n的。。。构成b数列。。。然后b数列的逆序对数小于等于k.问这样的l,r的对数。

思路:尺取+树状数组。

枚举l,每次找到最小的满足题意的r,对答案的贡献是n-r+1,然后用两个树状数组,分别维护增加或者减少一个树的时候,前半段和后半段对逆序数的影响。

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz