# 14213: 【原4213】排队

### 题目描述

author: Ge Yan 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4213

## Sample Input

``````8
9 5 1 6 2 7 3 8
``````

## Sample Output

``````13
``````

## Data Range

50%： n < 1000 100%: n < 300 000

## yyong119's solution

``````#include <cstdio>
using namespace std;
#define MAX_N 300010

long long ans;
int n;
int a[MAX_N];

void merge(int l, int r) {

int mid = (l + r) >> 1, i = l, j = mid + 1, k = l;
int tmp[MAX_N];
while (i <= mid && j <= r) {
if (a[i] <= a[j]) tmp[k++] = a[i++];
else {
ans += mid - i + 1;
tmp[k++] = a[j++];
}
}
while (i <= mid)
tmp[k++] = a[i++];
while (j <= r)
tmp[k++] = a[j++];
for (int i = l; i <= r; ++i)
a[i] = tmp[i];
}

void mergesort(int l, int r) {

if (l == r) return;
int mid = (l + r) >> 1;
mergesort(l, mid);
mergesort(mid + 1, r);
merge(l, r);
}

int main() {

scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
mergesort(1, n);
printf("%lld\n", ans);
return 0;
}
``````

## zqy2018's solution

``````/*
Hint: use Fenwick tree after discretization
*/
#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] = {0}, b[300005];
ll ans = 0;
int c[300005] = {0};
inline int lowbit(int x){
return x & (-x);
}
while(r <= n)
c[r] += v, r += lowbit(r);
}
int query(int r){
int res = 0;
while(r)
res += c[r], r -= lowbit(r);
return res;
}
void init(){
for (int i = 1; i <= n; ++i)
sort(b + 1, b + n + 1);
}
void solve(){
for (int i = n; i >= 1; --i){
int id = lower_bound(b + 1, b + n + 1, a[i]) - b;
ans += query(id - 1);