Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- long long arr[200001];
- long long ans;
- void merge(long long izq,long long mid,long long der){
- long long pos=0,posini=izq,ini2=mid+1;
- long long arrtemp[der-izq+1];
- while(izq<=mid&&ini2<=der){
- if(arr[izq]<=arr[ini2])
- arrtemp[pos++]=arr[izq++];
- else{
- ans=ans+(mid-izq+1);
- arrtemp[pos++]=arr[ini2++];
- }
- }
- while(izq<=mid) arrtemp[pos++]=arr[izq++];
- while(ini2<=der) arrtemp[pos++]=arr[ini2++];
- for(long long i=0;i<pos;i++)
- arr[posini+i]=arrtemp[i];
- return;
- }
- void mergeSort(long long izq,long long der){
- long long mid=(izq+der)/2;
- if(izq<der){
- mergeSort(izq,mid);
- mergeSort(mid+1,der);
- merge(izq,mid,der);
- }
- }
- int main(){
- long long ncases,nelem;
- cin>>ncases;
- while(ncases--){
- ans=0;
- cin>>nelem;
- for(int i=0;i<nelem;i++)
- cin>>arr[i];
- mergeSort(0,nelem-1);
- cout<<ans<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment