WA30
求逆序对
题目ID：1394必做题100分
最新提交：
Wrong Answer
30 分
历史最高：
Wrong Answer
30 分
时间限制: 1000ms
空间限制: 65536kB
题目描述
给出n个数的序列A, 定义逆序对(i, j)为满足：A[i]>Aj的数对。
输入格式：
第一行一个数，表示已知数的个数
第二行到第N+1行每行一个数
输出格式：
一个数，逆序数对的个数
样例输入
4
6
8
5
3
样例输出
5
数据规模：
a[i],n<=100000
时间限制：
1S
空间限制：
64M
WA30的代码：
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int MAX_N=1e5+10;
const int MX=100;
const ll BASE=131;
const ll MOD=1e9+7;
const int mxN=84;
const int mxK=14;
const int MAXSIZE=300;
int n=1e5,d[MAX_N],ans=0;
int lowbit(int x){return x&(-x);}
int ps(int i){
int res=0;
while(i){
res+=d[i];
i-=lowbit(i);
}
return res;
}
void padd(int i,int x){
while(i<=n){
d[i]+=x;
i+=lowbit(i);
}
}
int main(){
int m;
cin>>m;
for(int i=1,j;i<=m;i++){
cin>>j;
padd(j,1);
ans+=i-ps(j);
}
cout<<ans;
return 0;
}
