目录
问题引入
(洛谷P1908)[https://www.luogu.com.cn/problem/P1908],简单来说就是给一个数列,求出逆序对的数量
思路一览
BF做法
:遍历数组中的每一个数,对于每一个数,再次遍历前面的数,时间复杂度是n2归并排序
:这个...,不太了解,以后明白了再填坑权值树状数组
:由第一个的BF可以得出结论,对于每一个数,只需要求出它的前面有多少个数大于他即可,我们将数组进行从小到大的排序,并对原下标做处理,这样就是只需要求前缀和即可,求前缀和就是基本的树状数组题目了
具体情况
按照上面的说法其实还是有点模糊,下面简单扯几句(不然这篇博客太短了emmm)。对于一个已经排好序的序列(降序),毫无疑问,在前面的就是大于在后面的,假如这个时候我们要求一个位置i上的数前面有多少个大于它的数,那么就是i-1,i-1从和而来,不就是前面的i-1个数吗,假如我们把前面i-1个数中的一个移到i的后面去,这时候就会变成i-2,也就是说前面少了1;因此,我们对原数组进行降序排列,先加入数组的一定是更大的,将其加入到原数组的原索引位置上,对其求前缀和,那么得到的就是比他大的且索引比他小的数,观察数据范围,数列中的数的大小是1e9,采用离散化
的方法处理
code部分
#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define ll long long
#define ull unsigned long long
const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int N = 1e6+7;
int n, tmp, t[N];
int lowbit(int x) {return x&-x;}
pii a[N];
bool cmp(pii a, pii b) {
if(a.first != b.first) return a.first > b.first;
//假如两个数数值相同,要让索引小的后排在后面,否则这两个相同的也会计算成逆序对
return a.second > b.second;
}
void modify(int i, int x) {
//插入过后,对于该位置++, 表示这里多了一个数
for(; i <= n; i += lowbit(i)) t[i] += x;
}
int query(int i) {
int res = 0;
for(; i; i -= lowbit(i)) res += t[i];
return res;
}
void solve() {
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i].first, a[i].second = i;
sort(a+1, a+1+n, cmp);
ll ans = 0;
for(int i=1; i<=n; i++) {
ans += query(a[i].second-1);
modify(a[i].second, 1);
}
cout << ans << endl;
}
int main() {
#ifdef xrl
freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif
ios;
int t = 1;
//cin >> t;
while(t --) solve();
#ifdef xrl
cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";
#endif
return 0;
}
补充
补充,其实没有补充,今天是摸鱼的一天,苏福(bushi)
标签:const,int,first,数组,权值,逆序,例题,define From: https://www.cnblogs.com/notalking569/p/17990692