首页 > 代码库 > Codeforces Round #261 (Div. 2) D. Pashmak and Parmida's problem （树状数组求逆序数 变形）
Codeforces Round #261 (Div. 2) D. Pashmak and Parmida's problem （树状数组求逆序数 变形）
题目链接
题意：
给出一些数a[n]，求(i, j), i<j 的数量，使得：f(1, i, a[i]) > f(j, n, a[j]) 。
f(lhs, rhs, x) 指在 { [lhs, rhs]范围中，a[k]的值=x } 的数量。
1. f(1, i, a[i]) 就是指a[i]前面包括a[i]的数中，有几个值=a[i]。
2. f(j, n, a[j]) 就是指a[j]后面包括a[j]的数中有几个值=a[j]。
虽然a[x]范围不小，但是n的范围是1000，不是很大，所以我们可以用map预处理出 f(1, i, a[i]) 和 f(j, n, a[j]) ，记为s1[n], s2[n]。
这样就变成求满足 s1[i] > s[j]， i < j 情况的数量了,你会发现跟求逆序对一样
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。