逆序数 题解

逆序对模板题/x(怎么又是模板题啊)

题目大意：

给你一个长度为n的序列，求逆序对数

直接上归并排序。。。才怪。。。

作为一个热衷于权值线段树的菜鸡，当然直接上权值线段树辣！

只需要实现insert()添加一个数和find()查询值的范围属于查询区间的数字的个数

这两个基本函数就行。

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int W[N<<2];
inline void insert(int now,int l,int r,int x){
    ++W[now];
    if(l==r)return;
    int mid=(l+r)>>1;
    if(x<=mid)insert(now<<1,l,mid,x);
    else insert(now<<1|1,mid+1,r,x);
}
inline int find(int now,int l,int r,int lc,int rc){
    if(lc<=l&&r<=rc)return W[now];
    int mid=(l+r)>>1,res=0;
    if(lc<=mid)res+=find(now<<1,l,mid,lc,rc);
    if(rc>mid)res+=find(now<<1|1,mid+1,r,lc,rc);
    return res;
}
int main(){
    int n;long long res=0;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int x;
        scanf("%d",&x);++x;
        if(x!=N)res+=find(1,1,N,x+1,N);
        insert(1,1,N,x);
    }
    printf("%lld",res);
    return 0;
}