chenmou2012 @ 2024-03-10 19:52:26
#include<bits/stdc++.h>
using namespace std;
long long ans=0;
vector<int> vmerge;
void PrintVector(const vector<int>& vi){
for(auto i:vi){
cout<<i<<" ";
}
}
void merge(vector<int>& vi,int f1,int l1,int f2,int l2){
vmerge.resize(0);
int start = f1;
while(f1<=l1 && f2<=l2){
if(vi[f1]<=vi[f2]){
vmerge.push_back(vi[f1]);
f1++;
}else{
vmerge.push_back(vi[f2]);
f2++;
ans+=l1-f1+1;
}
}
if(f1<=l1){
for (int i = 0; i <= l1; ++i) {
vmerge.push_back(vi[i]);
}
}
if(f2<=l2){
for (int i = 0; i <= l2; ++i) {
vmerge.push_back(vi[i]);
}
}
for (int i = 0; i < vmerge.size(); ++i) {
vi[start+i] = vmerge[i];
}
}
void MergeSort(vector<int>& vi,int f,int l){
int size;
int ls;
int n=vi.size();
for (size = 1; size<=n-1; size*=2) {
for(ls=0;ls<n-1;ls+=2*size){
int mid=min(ls+size-1,n-1);
int rm = min(ls+2*size-1,n-1);
merge(vi,ls,mid,mid+1,rm);
}
}
}
int main(){
srand(time(0));
vector<int> vi;
// int n;cin>>n;
// for(int i=0;i<n;i++){
// int tmp;cin>>tmp;
// vi.push_back(tmp);
// }
int n;cin>>n;
for(int i=0;i<n;i++){
int tmp;cin>>tmp;
vi.push_back(tmp);
}
MergeSort(vi,0,vi.size()-1);
cout<<ans;
return 0;
}
by Sacred_Konnyaku_mMr @ 2024-03-10 20:46:16
把输入方式调快一点(cin换scanf)
把vector换成普通数组吧