P1908 逆序对
題目描述
貓貓TOM和小老鼠JERRY最近又較量上了，但是畢竟都是成年人，他們已經不喜歡再玩那種你追我趕的游戲，現在他們喜歡玩統計。最近，TOM老貓查閱到一個人類稱之為“逆序對”的東西，這東西是這樣定義的：對于給定的一段正整數序列，逆序對就是序列中ai>aj且i<j的有序對。知道這概念后，他們就比賽誰先算出給定的一段正整數序列中逆序對的數目。
輸入輸出格式
輸入格式：
?
第一行，一個數n，表示序列中有n個數。
第二行n個數，表示給定的序列。
?
輸出格式：
?
給定序列中逆序對的數目。
?
輸入輸出樣例
輸入樣例#1：?6 5 4 2 6 3 1 輸出樣例#1：?
11
說明
對于50%的數據，n≤2500
對于100%的數據，n≤40000。
?
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define date 100005 using namespace std;int n; long long ans; int num[date]; int sum[date];void merge_sort(int l,int r) {if(l<r){int mid=(l+r)/2;int x=l;int y=mid+1;int i=l;merge_sort(l,mid);merge_sort(mid+1,r);while(x<=mid||y<=r){if(y>r||(x<=mid&&num[x]<=num[y])){sum[i++]=num[x++];}else{sum[i++]=num[y++];ans+=mid-x+1;}}for(i=l;i<=r;i++){num[i]=sum[i];}} }void init() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&num[i]);}merge_sort(1,n);cout<<ans; }int main() {init();return 0; } 歸并排序 #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std;int n,ans,id[40005],c[40005]; struct NUM {int num,id; }num[40005];bool cmp(NUM a,NUM b) {return a.num>b.num; }int lowbit(int x) {return x&(-x); }void add(int x) {while(x<=n){c[x]++;x+=lowbit(x);} }int sum(int x) {int sum=0;while(x){sum+=c[x];x-=lowbit(x);}return sum; }int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&num[i].num);num[i].id=i; //離散化處理 }sort(num+1,num+n+1,cmp);for(int i=1;i<=n;i++){id[num[i].id]=i;}for(int i=1;i<=n;i++){ans+=sum(id[i]);add(id[i]);}printf("%d",ans);return 0; } BIT 樹狀數組 /*貌似是題解里唯一的一篇線段樹題解。本來是要做動態逆序對的，但是我不會cdq分治，樹狀數組和分塊不熟悉，所以想寫線段樹套線段樹。然后就先來用線段樹做一下不動態的。5倍空間消耗，比較慢，跑了近300ms 要離散化 指針+動態開點 */ #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std;const int N=4e4+5;int n,a,ans; struct Num {int num,id; }num[N],aha[N]; struct Node {Node *lson,*rson;int sum; }node[N<<2];typedef Node* Tree; Tree now_node,root,null;bool cmp1(Num a,Num b) {return a.num<b.num; }bool cmp2(Num a,Num b) {return a.id<b.id; }void init() {node->lson=node->rson=node;now_node=null=root=node; }int read() {char c=getchar();int num=0,f=1;for(;!isdigit(c);c=getchar());for(;isdigit(c);c=getchar())num=num*10+c-'0';return num; }Tree newNode() {++now_node;now_node->lson=now_node->rson=null;return now_node; }int query(Tree &root,int l,int r,int L,int R) {if(root==null)return 0;if(L<=l&&r<=R)return root->sum;int mid=l+r>>1;int ret=0;if(L<=mid)ret+=query(root->lson,l,mid,L,R);if(mid<R)ret+=query(root->rson,mid+1,r,L,R);return ret; }void modify(Tree &root,int l,int r,int pos) {if(root==null)root=newNode();if(l==r){root->sum=1;return;}int mid=l+r>>1;if(pos<=mid)modify(root->lson,l,mid,pos);elsemodify(root->rson,mid+1,r,pos);root->sum=root->lson->sum+root->rson->sum; }int main() {//freopen("testdata.in","r",stdin); init();n=read();for(int i=1;i<=n;++i){num[i].num=read();num[i].id=i;aha[i].id=i;}sort(num+1,num+n+1,cmp1);for(int i=1;i<=n;++i) //離散化，按大小編新的編號 aha[num[i].id].num=i;//sort(aha+1,aha+n+1,cmp2); //按輸入順序排序，還原原序列 for(int i=1;i<=n;++i){ans+=query(root,1,n,aha[i].num,n); //查找在它之前的比它大的數 modify(root,1,n,aha[i].num); //標記一下這個數已經出現 }printf("%d",ans);return 0; } 線段樹?
轉載于:https://www.cnblogs.com/lovewhy/p/8463526.html
總結
