Evanyou Blog 彩带

逆序对

题目描述

猫猫TOM和小老鼠JERRY最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。最近，TOM老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中ai>aj且i<j的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。

输入输出格式

输入格式：

第一行，一个数n，表示序列中有n个数。

第二行n个数，表示给定的序列。

输出格式：

给定序列中逆序对的数目。

输入输出样例

输入样例#1：复制

6
5 4 2 6 3 1

输出样例#1：复制

说明

对于50%的数据，n≤2500

对于100%的数据，n≤40000。

　　分析：

　　用归并或者树状数组都可以轻易A掉，但是这里用权值线段树。可以算是一道权值线段树的模板题。用于理解权值线段树。

　　Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
int n,p[maxn];ll ans;
struct Num{
    int id,val;
}a[maxn];
struct Seg{
    int l,r;ll val;
}seg[maxn<<2];
inline void pushup(int rt)
{
    seg[rt].val=seg[rt<<1].val+seg[rt<<1|1].val;
}
inline void build(int l,int r,int rt)
{
    seg[rt].l=l,seg[rt].r=r;
    if(l==r){seg[rt].val=0;return;}
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
}
inline void update(int rt,int x)
{
    if(seg[rt].l==seg[rt].r&&seg[rt].l==x){
        seg[rt].val++;return;}
    int mid=(seg[rt].l+seg[rt].r)>>1;
    if(x<=mid)update(rt<<1,x);
    if(x>mid)update(rt<<1|1,x);
    pushup(rt);
}
inline ll quary(int rt,int l,int r)
{
    if(seg[rt].l>r||seg[rt].r<l)return 0;
    if(l<=seg[rt].l&&seg[rt].r<=r)
        return seg[rt].val;
    int mid=(seg[rt].l+seg[rt].r)>>1;int ret=0;
    if(l<=mid)ret+=quary(rt<<1,l,r);
    if(r>mid)ret+=quary(rt<<1|1,l,r);
    return ret;
}
bool cmp(Num x,Num y)
{return x.val<y.val;}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    build(1,maxn,1);
    for(int i=1;i<=n;i++)
        cin>>a[i].val,a[i].id=i;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
         p[a[i].id]=i;
    for(int i=1;i<=n;i++){
        ans+=quary(1,p[i]+1,maxn);
        update(1,p[i]);}
    cout<<ans<<"
";
    return 0;
}