原题链接
题解1
本质：求一个数前面有几个数大于它，我们把序列分成几段，然后对每段分别进行排序，然后找出这个数在前面已经排好序中的序列里有几个大于它
code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[500005], b[500005], c[500005]; // a-original, b-replace, c-new
ll ans = 0;
inline void read(ll &x) {
x = 0;
ll flag = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-')flag = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
x *= flag;
}
inline void write(ll x)
{
if(x < 0){
putchar('-');
x = -x;
}
if(x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
void bg(ll l, ll r)
{
if (l == r) return;
ll mid = (l + r) / 2;
bg(l, mid);
bg(mid + 1, r);
ll p1 = l, p2 = mid + 1, p3 = l;
while (p1 <= mid && p2 <= r)
{
if (c[p1] <= c[p2]) b[p3++] = c[p1++];//为什么要等于？因为等于不算逆序对
else
{
b[p3++] = c[p2++];
ans += mid - p1 + 1;
}
}
while (p1 <= mid) b[p3++] = c[p1++];
while (p2 <= r) b[p3++] = c[p2++];
for (ll i = l; i <= r; i++) c[i] = b[i];
return;
}
int main()
{
ll n;
read(n);
for (ll i = 1; i <= n; i++)
{
read(a[i]);
c[i]=a[i];
}
bg(1, n);
write(ans);
return 0;
}
题解2：
设遍历到 \(i\) 则求已经出现的大于 \(a[i]\) 的数的个数 \(\to\) 求大于 \(a[i]\) 的数出现了几个，这样就变成了区间查询，然后 \(a[i]\) 出现代表单点修改，这样我们就就可以用树状数组来解题了，注意由于 \(a[i]\) 太大，所以还要离散化
code
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#define lowbit(x) ((x)&(-x))
using namespace __gnu_pbds;
using namespace std;
int a[500005],c[500005];
int b[500005]={0};
int n;
int len=0;
int query(int x)
{
int sum=0;
while(x)
{
sum+=b[x];
x-=lowbit(x);
}
return sum;
}
void update(int x)
{
while(x<=len)
{
b[x]++;
x+=lowbit(x);
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
c[i]=a[i];
}
sort(a+1,a+n+1);
gp_hash_table<int, int> id;
for(int i=1;i<=n;i++)
{
if(!id[a[i]]) id[a[i]]=++len;
}
int ans=0;
for(int i=1;i<=n;i++)
{
update(id[c[i]]);
ans+=i-query(id[c[i]]);//i represent the vals that have appeared,query() function gets the number of vals smaller than a[i] that have appeared
}
cout<<ans;
return 0;
}
