codeforces 459 D. Pashmak and Parmida’s problem (离散化+线段树求逆序对数)

题目链接
题意:定义f(l, r, x)为区间[l,r]中x出现的次数。现在要求calculate the number of pairs of indicies i, j (1 ≤ i < jn) such thatf(1, i, ai) > f(j, n, aj).

思路:可以通过o(n)预处理出f(1,i,a[i])和f[j,n,a[j]],其实预处理的过程就是离散化的过程呢。。。

分别得到

1 1 2 3 2 3 4

4 3 3 2 2 1 1

所以答案其实就是第一组数在第二组数中找逆序数的过程。。。

我们不妨倒序处理。

需要注意的是,线段树维护的区间是0..mx,我整体增加了1.

线段树求逆序对和树状数组求逆序对是同样的思想。。。注意体会。。

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz