14213: 【原4213】排队

题目描述

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

Description

从小老师就告诉我们排队的时候要从矮到高，但是总有一些同学喜欢随便站，这样就给老师造成了很大的困扰。于是聪明的老师就想出了一个办法，对于每一个学生，如果他的身后有比他矮的同学，那么他就要被罚糖，而且他身后有多少比他矮的同学就要罚多少颗糖。今天上体育课的时候同学们又站成了参差不齐的一列，老师希望你告诉他他总共能获得多少颗糖。

Input Format

第一行有一个整数N，代表有多少同学。第二行N个数表示N个同学的身高，按照他们现在的顺序排列。

Output Format

一个整数，代表老师能获得多少糖。

Sample Input

8
9 5 1 6 2 7 3 8

Sample Output

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 read(){
    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);
}
void add(int r, int v){
    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(){
    n = read();
    for (int i = 1; i <= n; ++i)
        a[i] = b[i] = read();
    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);
        add(id, 1);
    }
    printf("%lld\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}