首页 > > 程序设计 > C/C++ >

【luogu 1908】逆序对

2018-06-17 21:46:23来源：未知阅读 ()

题目描述

猫猫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。

树状数组（要离散化）：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define maxn 40005
 6 using namespace std;
 7 int read(){
 8     int x=0,f=1;char ch=getchar();
 9     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
10     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
11     return x*f;
12 }
13 int n,ans=0,c[maxn],b[maxn];
14 int lowbit(int x){return x&(-x);}
15 void add(int pos,int x){
16     while(pos<=n){
17         c[pos]+=x;
18         pos+=lowbit(pos);
19     }
20 }
21 int getsum(int pos){
22     int ans=0;
23     while(pos>0){
24         ans+=c[pos];
25         pos-=lowbit(pos);
26     }
27     return ans;
28 }
29 struct node{
30     int w,id;
31     bool operator < (const node &a) const{
32         return w<a.w;
33     }
34 }a[maxn];
35 int main(){
36     n=read();
37     for(int i=1;i<=n;i++){
38         a[i].w=read();
39         a[i].id=i;
40     }
41     sort(a+1,a+n+1);
42     int cnt=0;
43     b[a[1].id]=++cnt;
44     for(int i=2;i<=n;i++){
45         if(a[i-1].w!=a[i].w) b[a[i].id]=++cnt;
46         else b[a[i].id]=cnt;
47     }
48     for(int i=1;i<=n;i++){
49         add(b[i],1);
50         ans+=(getsum(n)-getsum(b[i]));
51     }
52     printf("%d",ans);
53     return 0;
54 }

归并排序：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 int read(){
 7     int x=0,f=1;char ch=getchar();
 8     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 9     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
10     return x*f;
11 }
12 int n,a[40004],rr[40004],ans=0;
13 void merge(int l,int r){
14     if(l==r) return ;
15     int mid=(l+r)>>1;merge(l,mid);merge(mid+1,r);
16     int t1=l,t2=mid+1,cnt=0;
17     while(t1<=mid&&t2<=r){
18         if(a[t1]<a[t2])
19             rr[++cnt]=a[t1],t1++;
20         else{
21             rr[++cnt]=a[t2],t2++;
22             ans+=mid-t1+1;
23         }
24     }
25     while(t1<=mid) rr[++cnt]=a[t1],t1++;
26     while(t2<=mid) rr[++cnt]=a[t2],t2++;
27     for(int i=1;i<=cnt;i++) a[l+i-1]=rr[i];
28 }
29 int main(){
30     n=read();for(int i=1;i<=n;i++)a[i]=read();
31     merge(1,n);
32     printf("%d",ans);
33     return 0;
34 }

线段树（要离散化）：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define maxn 40005
 6 #define ll l,mid,rt<<1
 7 #define rr mid+1,r,rt<<1|1
 8 using namespace std;
 9 int read(){
10     int x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 int sum[maxn<<2],b[maxn<<2];
16 struct node{
17     int w,id;
18     bool operator < (const node &a) const{
19         return w<a.w;
20     }
21 }a[maxn<<2];
22 void build(int l,int r,int rt){
23     if(l==r){
24         sum[rt]=0;
25         return ;
26     }
27     int mid=(l+r)>>1;
28     build(ll);build(rr);
29     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
30 }
31 int query(int ql,int qr,int l,int r,int rt){
32     if(ql<=l&&r<=qr)
33         return sum[rt];
34     int mid=(l+r)>>1;
35     int ans=0;
36     if(ql<=mid) ans+=query(ql,qr,ll);
37     if(mid<qr) ans+=query(ql,qr,rr);
38     return ans;
39 }
40 void update(int pos,int l,int r,int rt){
41     if(l==r){
42         sum[rt]=1;
43         return ;
44     }
45     int mid=(l+r)>>1;
46     if(pos<=mid) update(pos,ll);
47     else update(pos,rr);
48     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
49 }
50 int main(){
51     int n;
52     n=read();
53     for(int i=1;i<=n;i++){
54         a[i].w=read();
55         a[i].id=i;
56     }
57     sort(a+1,a+n+1);
58     int cnt=0;
59     b[a[1].id]=++cnt;
60     for(int i=2;i<=n;i++){
61         if(a[i-1].w!=a[i].w) b[a[i].id]=++cnt;
62         else b[a[i].id]=cnt;
63     }
64     build(1,n,1);
65     int ans=0;
66     for(int i=1;i<=n;i++){
67         ans+=query(b[i],n,1,n,1);
68         update(b[i],1,n,1);
69     }
70     printf("%d",ans);
71     return 0;
72 }