1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| vector<long> dt;
long msort(long l,long r){
if(l>=r-1) return 0;
long mid=(l+r)/2,j=mid;
long sum=msort(l,mid)+msort(mid,r);
long tmp[r-l],k=0;
for(long i=l;i<mid;i++){
while(j<r && dt[j]<dt[i]){
tmp[k++]=dt[j++];
}
tmp[k++]=dt[i];
sum+=j-mid;
}
while(j<r){
tmp[k++]=dt[j++];
}
j=0;
for(long i=l;i<r;i++){
dt[i]=tmp[j];
j++;
}
return sum;
}
|