Description
hzwer在研究逆序对。对于数列{a},如果有序数对(I,j)满足:i < j,a[i] > a[j],则(i,j)是一对逆序对。给定一个数列{a},求逆序对个数。 输入数据较大,请使用scanf代替cin读入。 *为防卡评测,时限调低至1s
第一行一个数n,表示{a}有n个元素。接下来n个数,描述{a}。
Output
一个数,表示逆序对个数。
5
3 1 5 2 4
Sample Output
4
Data
对于10%数据,1<=n<=100. 对于20%数据,1<=n<=10000. 对于30%数据,1<=n<=100000. 对于100%数据,1<=n<=1000000,1<=a[i]<=10^8.
I think
本意是权值线段树求逆序对的模板,然而线段树TLE六个点相较之下树状数组跑得飞起。
Code
#include<cstdio>
#include<algorithm>
#define lowbit(x) x&(-x)
using namespace std;
typedef long long ll;
const int sm =
1e6+
50;
int n,t;
ll s,ans,tot[sm];
struct lsh {
ll val;
int a,b;
}x[sm];
char ch;
template <
typename T>
void read(T &x) {
x=
0,ch=getchar();
while(ch>
'9'||ch<
'0') ch=getchar();
while(ch>=
'0'&&ch<=
'9') x=x*
10+ch-
'0',ch=getchar();
}
bool ca(lsh x,lsh y) {
return x.val<y.val;
}
bool cb(lsh x,lsh y) {
return x.a<y.a;
}
ll query(
int x) {
s=
0;
for(
int i=x;i;i-=lowbit(i))
s+=tot[i];
return s;
}
void add(
int x,
int y) {
for(
int i=x;i<=n;i+=lowbit(i))
tot[i]=
1ll*(tot[i]+y);
}
int main() {
read(n);
for(
int i=
1;i<=n;++i)
read(x[i].val),x[i].a=i;
sort(x+
1,x+n+
1,ca);
for(
int i=
1;i<=n;) {
while(x[i].val==x[i-
1].val)
x[i].b=x[i-
1].b,++i;
x[i++].b=++t;
}
sort(x+
1,x+n+
1,cb);
for(
int i=
1;i<=n;++i) {
ans+=query(t)-query(x[i].b);
add(x[i].b,
1);
}
printf(
"%lld\n",ans);
return 0;
}