Skip to content

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

题目

题目描述

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

题目描述

对于一个给定n个数的序列\( a_1, a_2, \cdots, a_n \) ,定义一个数对\( (a_i, a_j) \)称为逆序对当且仅当\( i < j \bigwedge a_i > a_j \).

可是人们感觉这个度量可能太敏感了,因此人们又定义一个数对 \( (a_i, a_j) \)称为重要的逆序对当且仅当 \( i < j \bigwedge a_i > 2 a_j \).

你的任务就是找出给定序列的重要的逆序对数目。

输入

第1行:一个数n,表示序列的长度,

第2-n+1行,每行一个数,表示序列从前到后的每个数 \( a_1, a_2, \cdots, a_n \)。

输出

第1行:一个数M,表示给定序列的重要的逆序对数目。

Sample input

5  
9  
3  
5  
3  
1

Sample output

6

Limits

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

Timelimits

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