逆序对求调

meiweid_quanyiang @ 2024-10-06 14:50:08

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

by meiweid_quanyiang @ 2024-10-06 14:52:24

超时了，n<=10e5

by fang_putao @ 2024-10-06 15:03:01

@meiweid_quanyiang

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    for(int i = 1;i * i <= n;i ++)
        cout << i * i << " ";
    return 0;
}

by fang_putao @ 2024-10-06 15:04:11

正确答案(非常短对吧)@meiweid_quanyiang

by meiweid_quanyiang @ 2024-10-06 15:09:29

@fang_putao 这不是输出n以内的完全平方数吗？

by meiweid_quanyiang @ 2024-10-06 15:12:23

快读快写也没用

#include<bits/stdc++.h>
using namespace std;
int a[200010],n,tmp[200010];
long long ans=0;
inline int read(){
    register int x = 0, t = 1;
    register char ch=getchar(); // 读入单个字符到寄存器
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            t=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);  // 移位与异或
        // 第十行可以换成 x = x * 10 + ch - '0'
        ch=getchar();
    }
    return x*t;
}
inline void write(int x)
{
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) 
        write(x/10);
    putchar(x%10+'0');
}
void merge_sort(int l,int r){
    if(l==r)return;
    int mid=(l+r)/2;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    int i=l,j=mid+1,k=l; 
    while(i<=mid&&j<=r){
        if(a[i]>a[j]){
            ans+=mid-i+1;
            tmp[k++]=a[j++];
        }
        else{
            tmp[k++]=a[i++];
        }
    }
    while(i<=mid){
        tmp[k++]=a[i++];
    }
    while(j<=r){
        tmp[k++]=a[j++];
    }
    for(int i=0;i<k;i++)a[i]=tmp[i]; 
    return;
}
int main(){
    n=read();
    for(int i=0;i<n;i++){
        a[i]=read();
    }
    merge_sort(0,n-1);
    write(ans);
} 

by fang_putao @ 2024-10-06 15:18:14

@meiweid_quanyiang嗯，就是完全平方数

by jimmy0926 @ 2024-11-03 14:30:01

@meiweid_quanyiang look at this.

for(int i=0;i<k;i++)a[i]=tmp[i];

maybe like this.

a[i + l] = tmp[i];