只是为了记录求逆序对的一种解法用线段树+离散化进行求解
先将线段树的板子默写下来,然后,我们只需要稍加改动即可ac此题
就是我们在求逆序对的个数的时候,是边进行插入,边进行查询
逆序对是什么,就是i>j而a[i]<a[j]
这个i,j下标我们可以理解成出现的时间
比如有一个数列为4 3 1 2
我们从前往后进行扫描,首先我们插入4
因为是求逆序对,所以我们要查询的是比4大的数
就是query(1,a[i]+1,n);
而我们又保证了在插入的时候,我们是按照时间插入的,也就是我们这个时候查询出来的比a[i]大的数,肯定是出现在a[i]之前的,所以也就符合了我们逆序对的定义
完结撒花
若有什么说的不对的地方,大佬轻喷
#include<bits/stdc++.h>
using namespace std;
const int N=300000;
int a[N],t[N];
int n;
int tong[N];
int big[N];
long long res;
struct node
{
int l,r;
}tr[N];
int date[N];
void pushup(int p)
{
date[p]=date[p<<1]+date[p<<1|1];
}
void build(int p,int l,int r)
{
tr[p]={l,r};
if(l==r) return ;
int mid=(l+r)/2;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
int query(int p,int l,int r)
{
if(l>r) return 0;
int ans=0;
if(tr[p].l>=l&&tr[p].r<=r)
{
return date[p];
}
int mid=(tr[p].l+tr[p].r)/2;
if(l<=mid) ans+=query(p<<1,l,r);
if(r>mid) ans+=query(p<<1|1,l,r);
return ans;
}
void update(int p,int x,int d)
{
if(tr[p].l==x&&tr[p].r==x)
{
date[p]+=d;
return ;
}
int mid=(tr[p].l+tr[p].r)/2;
if(x<=mid) update(p<<1,x,d);
if(x>mid) update(p<<1|1,x,d);
pushup(p);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
t[i]=a[i];
}
sort(t+1,t+1+n);
int m=unique(t+1,t+1+n)-t-1;
for(int i=1;i<=n;i++)
a[i]=lower_bound(t+1,t+1+m,a[i])-t;
build(1,1,n);
for(int i=1;i<=n;i++)
{
update(1,a[i],1);
big[i]=query(1,a[i]+1,n);
}
for(int i=1;i<=n;i++)
res+=big[i];
cout<<res<<endl;
return 0;
}