11354: 【原1354】lalala

题目

题目描述

author: yuan 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1354 

题目描述

我们定义一个N个数字的序列A，那么一个逆序对(i,j)满足i < j 且A[i] > A[j]。现给定一个长度为N的序列，请你求出逆序对的个数。

（如果一时没有什么思路，可以想想归并排序的做法）

输入说明

第一行一个数字N，第二行N个整数表示A序列。

输出格式

一行一个数字，表示逆序对个数。

Sample input

6 
1 2 4 5 3 6

Sample output

2

数据范围

对于100%的数据，1<=N<=100000(没有小数据，不要问为什么，我以前很懒，忘记出小数据了)

对于60%的数据，1<=N<=1000

对于100%的数据，1<=N<=100000

yyong119's solution

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX_N 100010
#define lowbit(x) (x & (-x))
using namespace std;
int n, cnt;
long long ans;
int a[MAX_N], b[MAX_N], c[MAX_N];
inline int read() {
    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 << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    // return res * flag;
    return res;
}
inline void add(int x) {
    for (; x <= cnt; x += lowbit(x)) ++c[x];
}
inline int query(int x) {
    int res = 0;
    for (; x; x -= lowbit(x)) res += c[x];
    return res;
}
int main() {
    n = read();
    for (register int i = 0; i < n; ++i)
        a[i] = read();
    memcpy(b, a, sizeof(a));
    sort(b, b + n);
    cnt = unique(b, b + n) - b;
    for (register int i = 0; i < n; ++i) {
        a[i] = lower_bound(b, b + cnt, a[i]) - b + 1;
        ans += query(cnt) - query(a[i]);
        add(a[i]);
    }
    printf("%lld", ans);
    return 0;
}