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