Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- using namespace std;
- const int N = 65537 + 4;
- vector < long long > v(N);
- long long merge(int, int, int, int);
- long long merge_sort(int l, int r) {
- int mid = (l+r) >> 1;
- long long lInver = 0, rInver = 0, mergeInver = 0;
- if (l != mid) {
- lInver = merge_sort(l, mid);
- }
- if (r != mid+1) {
- rInver = merge_sort(mid+1, r);
- }
- if (r != l) {
- mergeInver = merge(l, mid, mid+1, r);
- }
- return mergeInver + lInver + rInver;
- }
- long long merge(int l1, int r1, int l2, int r2) {
- vector < long long > temp(r2-l1+1);
- long long tInver = 0;
- int i = l1, j = l2, k = 0;
- while (i <= r1 && j <= r2) {
- if (v[i] <= v[j]) {
- temp[k] = v[i];
- ++i;
- }
- else {
- temp[k] = v[j];
- ++j;
- tInver += l2 - i;
- }
- ++k;
- }
- while (i <= r1) {
- temp[k++] = v[i++];
- }
- while (j <= r2) {
- temp[k++] = v[j++];
- }
- for (int k = 0, i = l1; i <= r2; ++i) {
- v[i] = temp[k++];
- }
- return tInver;
- }
- int main() {
- int t = 1;
- // cin >> t;
- while (t--) {
- int n;
- cin >> n;
- // n = 1e7;
- for (int i = 0; i < n; ++i) {
- cin >> v[i];
- }
- cout << merge_sort(0, n-1) << '\n';
- }
- }
Add Comment
Please, Sign In to add comment