XDOJ-1617

思路

动手模拟一遍。

发现了，对于第一层循环的 $i$ ，前 $i-1$ 个数一定是有序的，那么当前的 $i$ 对答案的贡献即为 $a_1\sim a_{i-1}$ 内比 $a_i$ 大的数的个数，即 $i$ 之前的包含 $a_i$ 的逆序对的个数。

同时可以发现，第一层循环为 $i$ 时，$a_{i+1}\sim a_n$ 是不动的，所以该部分对求上述的逆序对没有影响。

所以我们暴力进行 $i$ 等于 $1$ 的排序后，直接顺次来求逆序对即可。

由于值域过大，所以可以考虑离散化+线段树或者动态开点线段树。

我写的动态开点线段树，时间复杂度 $O(n\log L)$ ， $L$ 为值域。

代码

#include<bits/stdc++.h>
#define N 200010
#define MAXN 1000000000
#define Log 32
#define ll long long 

using namespace std;

inline int read() {
    int w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int n,a[N];
ll ans=0;

int root=0,tot=0;
class SegmentTree{
  private:
    int sum[N*Log],ls[N*Log],rs[N*Log];
    #define s(p) sum[p]
    #define ls(p) ls[p]
    #define rs(p) rs[p]
    #define mid (l+r>>1)
    void update(int p) {
        s(p)=s(ls(p))+s(rs(p));
    }
  public:
    void change(int &p,int l,int r,int x) {
        if(l>x||r<x) return ;
        if(!p) p=++tot;
        if(l==r) {
            s(p)=1;
            return ;
        }
        change(ls(p),l,mid,x),change(rs(p),mid+1,r,x);
        update(p);
    }
    int ask(int p,int l,int r,int L,int R) {
        if(l>R||r<L) return 0;
        if(l>=L&&r<=R) return s(p);
        return ask(ls(p),l,mid,L,R)+ask(rs(p),mid+1,r,L,R);
    }
}SMT;

int main() {
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) {
        if(a[i]>a[1]) {
            swap(a[1],a[i]);
            ans++;
        }
    }
    for(int i=1;i<=n;i++) {
        ans+=SMT.ask(root,1,MAXN,a[i]+1,MAXN);
        SMT.change(root,1,MAXN,a[i]);
    }
    printf("%lld\n",ans);
    system("pause");
    return 0;
}