给我点差评的煤油浮木，没油机吧，每有厚带

给我点好评的长命百岁，身体健康，每次比赛都会过

题意:

归并+逆序对

思路:

归并+逆序对

如果学过也不知道逆序对是什么就是你没学懂

呆 代码:

#include<iostream>
using namespace std;
int n,a[114514],b[114514];
long long cnt=0;//要long long
void me(int l,int m,int r)//三个参数
{
	int i=l,j=m+1,bi=l;//左边和右边和数组指针
	while(i<=m && j<=r)//都没有结束时
	{
		if(a[i]<=a[j])//a[i]<=a[j]时
		{
			b[bi++]=a[i++];//入数组
		}
		else
		{
			b[bi++]=a[j++];//入数组
			cnt+=m-i+1;//计数
		}
	}
	while(i<=m)//到i结束时
	{
		b[bi++]=a[i++];//入数组
	}
	while(j<=r)//到j结束时
	{
		b[bi++]=a[j++];//入数组
	}
	for(int k=l;k<=r;k++)
	{
		a[k]=b[k];//copy
	}
}
void f(int l,int r)
{
	if(l<r)//有区间时
	{
		int m=(l+r)/2;//一半
		f(l,m);//左边
		f(m+1,r);//右边
		me(l,m,r);//排序+copy
	}
}
int main()
{
	cin>>n;//输入
	for(int i=0;i<n;i++)
	{
		cin>>a[i];//输入
	}
	f(0,n-1);//排序
	cout<<cnt;//输出
	return 0;//完结散花
}

题意

求数组里的逆序对个数

逆序对：当 $i$ 小于 $j$ 且 $a_i < a_j$ 时，$a_i$ 与 $a_j$ 为逆序对

PS：$i$ 小于 $j$ 就行，不用相邻

思路

归并排序过程中顺便求出答案

演示图

当 $a_j$（右边区间的某个数）小于 $a_i$（左边区间的某个数），那么在 $a_i$ 右边的所有数将都比 $a_j$ 大，所以逆序对个数增加 $(mid-n+1)$ 个

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int a[N],b[N],cnt;
void msort(int l,int r){
	if (l >= r)	return;
	int m = (l + r) >> 1;
	msort(l,m);
	msort(m + 1,r);

	int i = l,j = m + 1,idx = l;
	while (i <= m && j <= r){
		if (a[i] > a[j]){
			b[idx++] = a[j++];
			cnt += m - i + 1;
		}else	b[idx++] = a[i++];
	}
	while (i <= m)	b[idx++] = a[i++];
	while (j <= r)	b[idx++] = a[j++];
	for (int i = l;i <= r;i++)	a[i] = b[i];
}
signed main(int argc, char **argv){
	int n;
	cin >> n;
	for (int i = 0;i < n;i++){
		cin >> a[i];
	}
	msort(0,n - 1);
	cout << cnt;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
long long a[100005],b[100005],x=0;
int n;
void merge(int l,int mid,int r){
	int i=l,j=mid+1,t=l;
	while(i<=mid&&j<=r){
		if(a[i]<=a[j]) b[t++]=a[i++];
		else {
			b[t++]=a[j++];
			x+=mid-i+1;
		}
	}
	while(i<=mid) b[t++]=a[i++];
	while(j<=r) b[t++]=a[j++];
	for(int i=l;i<=r;i++) a[i]=b[i];
}
void msort(int l,int r){
	if(l>=r) return;
	int mid=(l+r)>>1;
	msort(l,mid);
	msort(mid+1,r);
	merge(l,mid,r);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	} 
	msort(1,n);
	cout<<x;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
long p[100010],tmp[100010],psum,n;
void merge(int l,int r){
	if(l>=r)return;
	int mid=(l+r)/2;
	merge(l, mid);
	merge(mid+1,r);
	int i=l,j=mid+1,k=0;
	while(i<=mid&&j<=r){
		if(p[i]<=p[j])tmp[k++]=p[i++];
		else{ 
			psum+=mid-i+1;
			tmp[k++]=p[j++];
		}
	}
	while(i<=mid)tmp[k++]=p[i++];
	while(j<=r)tmp[k++]=p[j++];
	for(i=l,j=0;i<=r;i++,j++)p[i]=tmp[j];
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++)cin>>p[i];
	merge(0,n-1);
	cout<<psum;
	return 0;
}

#include<iostream> 
using namespace std;
long long a[100001],b[100001],ds=0;
void merge(int l,int mid,int r){
    int i=l,j=mid+1,t=l;
    while(i<=mid&&j<=r){
    if(a[i]<=a[j]){
    b[t++]=a[i++];
    }
    else{
    b[t++]=a[j++];
    	ds=ds+mid-i+1;
    }
    }
    while(i<=mid){
    b[t++]=a[i++];
    }
    while(j<=r){
    b[t++]=a[j++];
    }
    for(int i=l;i<=r;i++){
    a[i]=b[i];
    }
}
void msort(int l,int r){
    if(l>=r){
    return;
    }
    int mid=(l+r)>>1;
    msort(l,mid);
    msort(mid+1,r);
    merge(l,mid,r);
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
    cin>>a[i];
    }
    msort(1,n);
    cout<<ds;
}

//如果·左区间：  5 6 7  
//右区间：  1 2 9  

//1：由于 5>1，所以产生了逆序对，这里，我们发现，左区间所有还没有被合并的数都比 1 大，所以1与左区间所有元素共产生了 3 个逆序对(即tot_numleft-i+1对)，统计答案并合并 1 
//2：由于 5>2，由上产生了3对逆序对，统计答案并合并 2
//3：由于 5<9, 没有逆序对产生，右区间下标 j++
//4：由于 6<9, 没有逆序对产生，右区间下标 j++
//5：由于 7<9, 没有逆序对产生，右区间下标 j++




#include<bits/stdc++.h> 
using namespace std;
#define int long long
// long long a[11561511];
const int N=1E5+1;
long long a[N],b[N],cyt=0;;
void guib(int left,int right){
   //归并
   if(left==right ){//区间已经有序
      return;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   //lancas Lancas
   }
   int le=left,centre=left/2+right/2,ri=centre+1;//le=左区间扫的指针 ri=左区间扫的指针 center是中间数 使用等差数列a+b/2求出                                          lancas Lancas
   int l2=left;
   guib(left,centre);//左区间
   guib(centre+1,right);//右区间
   while(le<=centre&&ri<=right){//是否扫完
      if(a[le]<=a[ri]){
         b[l2++]=a[le++];//组合成有序数组·
         // l2++;
         // le++;
      }
      else{
         b[l2++]=a[ri++];
         //cyt+=1
         cyt+=centre-le+1;


      }


   }
   while(le<=centre){//是否扫完
      // if(a[le]<a[ri]){
      //    b[l2++]=a[le++];
      //    // l2++;
      //    // le++;
      // }
      // else{
      //    b[l2++]=a[ri++];
      //    //cyt+=1
      //    cyt+=centre-i+1;
         

      // }
      b[l2++]=a[le++];



   }
   while(ri<=right){//是否扫完
      // if(a[le]<a[ri]){
      //    b[l2++]=a[le++];
      //    // l2++;
      //    // le++;
      // }
      // else{
      //    b[l2++]=a[ri++];
      //    //cyt+=1
      //    cyt+=centre-i+1;
         

      // }
      b[l2++]=a[ri++];



   }
   for(int i=left;i<=right;i++)//覆盖元素组
      a[i]=b[i];

}
signed main(){
   int n,cnt=0;
   cin>>n;
   for(int i=1;i<=n;i++){
      cin>>a[i];
   }
   // for(int i = 1; i <= n; i ++){
   //    for(int j = i; j <= n; j ++){
   //       if(a[i] > a[j])cnt ++;
   //    }
   // }
   guib(1,n);
   cout<<cyt;

   




   return 0; 
}

`#include<bits/stdc++.h> 
using namespace std;

long long a[114514], r[114514];
 long long ans = 0; 
void mosort (long long s, long long t)
 { 
	if(s == t) return ;
	long long mid = (s + t) / 2; 
	mosort(s, mid); 
	mosort(mid + 1, t); 
	int i = s, j = mid + 1, k = s; 
	while(i <= mid && j <= t) 
	{ 
		if(a[i] <= a[j]) 
		{ 
			r[k] = a[i];
			k++;
			i++; 
		} 
		else 
		{ 
			r[k] = a[j];
			k++;
			j++; 
			ans+=mid-i+1; 
		} 
	} 
	while(i <= mid)
	{
		r[k] = a[i];
		k++;
		i++;
	} 
	while(j <= t)
	{ 
		r[k] = a[j];
		k++;
		j++; 
	} 
	for(int i = s; i <= t; i++) a[i] = r[i];
}

int main() 
{
 	int n; 
	cin >> n;
 	for(int i = 1; i <= n; i++) 
	{
		cin >> a[i]; 
	}
	mosort(1,n); 
	cout << ans;
 	return 0; 
}`

来自一本通的标准答案 没有防抄袭代码 放心食用

#include<bits/stdc++.h> using namespace std;

long long a[114514], r[114514]; long long ans = 0; void mosort (long long s, long long t) { if(s == t) return ; long long mid = (s + t) / 2; mosort(s, mid); mosort(mid + 1, t); int i = s, j = mid + 1, k = s; while(i <= mid && j <= t) { if(a[i] <= a[j]) { r[k] = a[i];k++;i++; } else { r[k] = a[j];k++;j++; ans+=mid-i+1; } } while(i <= mid) { r[k] = a[i];k++;i++; } while(j <= t) { r[k] = a[j];k++;j++; } for(int i = s; i <= t; i++) a[i] = r[i]; }

int main() { int n; cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; mosort(1,n); cout << ans; return 0; }