11219: 【原1219】重要的逆序数对

题目描述

author: Fangkui Zhang 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1219

Sample input

``````5
9
3
5
3
1
``````

Sample output

``````6
``````

Limits

60%：N <= 5000 100%: N <= 200000

1000ms

yyong119's solution

``````#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX_N 200020
using namespace std;
int a[MAX_N << 1], b[MAX_N << 1], tree[MAX_N << 1];
int n, cnt;
long long ans;
char ch = getchar(); int flag = 1, res = 0;
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') flag = -1, ch = getchar();
while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
return res * flag;
}
inline void update(int x) {
for (; x <= cnt; x += x & -x)
++tree[x];
}
inline int query(int x) {
int res = 0;
for (; x; x -= x & -x)
res += tree[x];
return res;
}
int main() {
for (register int i = 0; i < n; ++i) {
a[i + n] = a[i] << 1;
}
memcpy(b, a, sizeof(a));
sort(b, b + (n << 1));
cnt = unique(b, b + (n << 1)) - b;
for (register int i = 0; i < (n << 1); ++i)
a[i] = lower_bound(b, b + cnt, a[i]) - b + 1;

update(a[0]);
for (register int i = 1; i < n; ++i) {
ans += (long long)query(cnt) - (long long)query(a[i + n]);
update(a[i]);
}
printf("%lld\n", ans);
return 0;
}
``````

zqy2018's solution

``````/*
See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu1219.md
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, a[300005];
ll ans = 0;
template <typename T>
void Msort_Merge(T* a, T* tmp, int l, int mid, int r){
int lpos = l, rpos = mid, pos = l;
int ppos = l;
while (lpos < mid && rpos < r){
if (a[lpos] <= a[rpos]) tmp[pos++] = a[lpos++];
else {
while (ppos < mid && a[ppos] <= 2 * a[rpos])
++ppos;
ans += mid - ppos;
tmp[pos++] = a[rpos++];
}
}
while (lpos < mid) tmp[pos++] = a[lpos++];
while (rpos < r) tmp[pos++] = a[rpos++];
for (int i = l; i < r; ++i)
a[i] = tmp[i];
}
template <typename T>
void Msort(T *a, T* tmp, int l, int r){
/* [l, r) */
if (r - l <= 1) return ;
int mid = (l + r) >> 1;
Msort(a, tmp, l, mid);
Msort(a, tmp, mid, r);
Msort_Merge(a, tmp, l, mid, r);
}
template <typename T>
void MergeSort(T *a, int n){
T *tmp = new T[n];
Msort(a, tmp, 0, n);
delete [] tmp;
}
void init(){