逆序对

题目描述

猫猫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+;

int n,p[maxn];ll ans;

struct Num{

    int id,val;

}a[maxn];

struct Seg{

    int l,r;ll val;

}seg[maxn<<];

inline void pushup(int rt)

{

    seg[rt].val=seg[rt<<].val+seg[rt<<|].val;

}

inline void build(int l,int r,int rt)

{

    seg[rt].l=l,seg[rt].r=r;

    if(l==r){seg[rt].val=;return;}

    int mid=(l+r)>>;

    build(l,mid,rt<<);

    build(mid+,r,rt<<|);

}

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)>>;

    if(x<=mid)update(rt<<,x);

    if(x>mid)update(rt<<|,x);

    pushup(rt);

}

inline ll quary(int rt,int l,int r)

{

    if(seg[rt].l>r||seg[rt].r<l)return ;

    if(l<=seg[rt].l&&seg[rt].r<=r)

        return seg[rt].val;

    int mid=(seg[rt].l+seg[rt].r)>>;int ret=;

    if(l<=mid)ret+=quary(rt<<,l,r);

    if(r>mid)ret+=quary(rt<<|,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(,maxn,);

    for(int i=;i<=n;i++)

        cin>>a[i].val,a[i].id=i;

    sort(a+,a+n+,cmp);

    for(int i=;i<=n;i++)

         p[a[i].id]=i;

    for(int i=;i<=n;i++){

        ans+=quary(,p[i]+,maxn);

        update(,p[i]);}

    cout<<ans<<"\n";

    return ;

}

巴特西

洛谷P1908 逆序对 [权值线段树]

逆序对

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章