SOMO @ 2024-12-01 14:02:06
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL count1=0;
#define N 500010
void Merge(int arr[],int tmp[],int l,int r,int mid){
for(int p=l;p<=r;p++){
tmp[p]=arr[p];
}
int i,j;
int k=l;
for(i=l,j=mid+1;i<=mid && r>=j;k++){
if(tmp[i]>tmp[j]){
arr[k]=tmp[j++];
count1+=mid - i + 1;
}
else if(tmp[j]>tmp[i])
arr[k]=tmp[i++];
}
while(i<=mid){
arr[k++]=tmp[i++];
}
while(j<=r){
arr[k++]=tmp[j++];
}
}
void MergeSort(int arr[],int tmp[],int l,int r){
if(l<r){
int mid=(l+r)/2;
MergeSort(arr,tmp,l,mid);
MergeSort(arr,tmp,mid+1,r);
Merge(arr,tmp,l,r,mid);
}
}
void Msort(int arr[],int n){
int* tmp=(int*)malloc(N*sizeof(int));
if(tmp!=NULL){
MergeSort(arr,tmp,0,n-1);
free(tmp);
}
else
cout<<"wrong"<<endl;
}
//快读
inline int read()
{
int w=1,ans=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){ans=ans*10+(ch-'0');ch=getchar();}
return w*ans;
}
int main(){
// int n;
// cin>>n;
int n=read();
int numbers[N];
for(int i=0;i<n;i++){
cin>>numbers[i];
}
Msort(numbers,n);
cout<<count1<<endl;
return 0;
}
by _yAy_ @ 2024-12-01 14:26:36
是不是函数调用太多，常数太大了？
by SOMO @ 2024-12-01 14:51:00
@yAy 我去试一下写进一个里面QAQ
by lly66666 @ 2024-12-02 20:32:18
六...
麦代码：
#include <bits/stdc++.h>
using namespace std;
int n, a[500005], c[500005];
long long ans;
void msort(int l, int r) {
if(l == r) return;
int mid = (l + r) / 2, i = l, j = mid + 1, k = l;
msort(l, mid), msort(mid + 1, r);
while (i <= mid && j <= r) {
if (a[i] <= a[j]) c[k++] = a[i++];
else {c[k++] = a[j++]; ans += mid - i + 1;}
}
while(i <= mid) c[k ++] = a[i ++];
while(j <= r) c[k ++] = a[j ++];
for(int i = l; i <= r; i ++) a[i] = c[i];
}
int main() {
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
msort(1, n);
cout << ans;
return 0;
}by luvsicpt @ 2024-12-26 19:50:26
@lly66666我的跟你差不多但是我的为啥不过啊
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5;
long long res;
int a[N],b[N];
void msort(int l,int r) {
if (l>=r)return;
long long mid=l+(r-l)/2;
msort(l,mid);
msort(mid+1,r);
int i=l,j=mid+1,k=l;
while (i<=mid&&j<=r) {
if (a[i]<=a[j]) {
b[k++]=a[i++];
}
if (a[i]>=a[j]){
b[k++]=a[j++];
res+=mid-i+1;
}
}
while (i<=mid) {
b[k++]=a[i++];
}
while (j<=r) {
b[k++]=a[j++];
}
for (int e=l;e<=r;e++) {
a[e]=b[e];
}
}
int main(){
int n;
cin>>n;
for (int i=1;i<=n;i++) {
cin>>a[i];
}
msort(1,n);
cout<<res;
return 0;
}by lly66666 @ 2024-12-26 19:55:36
我测一下
by lly66666 @ 2024-12-26 20:32:26
调了半天发现原来是数组没开够。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
long long res;
int a[N],b[N];
void msort(int l,int r) {
if (l==r)return;
int mid=(r+l)/2,i=l,j=mid+1,k=l;
msort(l,mid), msort(mid+1,r);
while (i<=mid&&j<=r) {
if (a[i]<=a[j]) { b[k++]=a[i++]; }
else{ b[k++]=a[j++]; res+=mid-i+1; }
}
while (i<=mid) b[k++]=a[i++];
while (j<=r) b[k++]=a[j++];
for (int i=l;i<=r;i++) a[i]=b[i];
}
int main(){
int n;
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];
msort(1,n);
cout<<res;
return 0;
}by luvsicpt @ 2024-12-26 20:40:23
@lly66666不对啊我在我原代码基础上加了五但是还是45啊
by lly66666 @ 2024-12-27 12:03:34
@luvsicpt
我有做标记的就是有改动的
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5; //
long long res;
int a[N],b[N];
void msort(int l,int r) {
if (l==r)return; //
int mid=(r+l)/2,i=l,j=mid+1,k=l;
msort(l,mid), msort(mid+1,r);
while (i<=mid&&j<=r) {
if (a[i]<=a[j]) { b[k++]=a[i++]; }
else{ b[k++]=a[j++]; res+=mid-i+1; } //
}
while (i<=mid) b[k++]=a[i++];
while (j<=r) b[k++]=a[j++];
for (int i=l;i<=r;i++) a[i]=b[i];
}
int main(){
int n;
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];
msort(1,n);
cout<<res;
return 0;
}by luvsicpt @ 2024-12-28 00:02:06
@lly66666我知道了，是那个判断大小的时候a[i]>=a[j]这步错了，该改成a[i]>a[j],因为前面判断了一次等于，我服了
by lly66666 @ 2024-12-28 11:32:25
@luvsicpt AC了吗？