Subtask ~1~

Dùng thuật toán quay lui để sinh ra tất cả các dãy có thể có, sau đó đếm số cặp nghịch thế trong mỗi dãy.Độ phức tạp: ~O(n^{15}\times15\times15)~.

Subtask ~2~

• Mỗi số ~a_i~ có ~2~ trường hợp:
  • ~a_i > 0~: số cặp nghịch thế chắc chắn tồn tại sẽ bằng số số ~a_j~ sao cho ~j > i~ và ~|a_j| < |a_i|~.
  • ~a_i < 0~: số cắp nghịch thế chắc chắn tồn tại sẽ bằng số số ~a_j~ sao cho ~j < i~ và ~|a_j| < |a_i|~.
• Độ phức tạp: ~O(n^2)~.

Subtask ~3~

Giống subtask ~2~ nhưng thay vì mất ~O(n^2)~ để đếm số cặp nghịch thế thì ta có thể dùng ~BIT~ hoặc ~IT~. Độ phức tạp: ~O(nlogn)~.

Code tham khảo

typedef long long ll;

const int N = 1e5 + 5;
int a[N], b[N], cnt[N], ans = 0;
int n;

void update(int x, int val){
    for(; x <= N; x += x&-x)
        b[x] += val;
}

int get(int x){
    int res = 0;
    for(; x >= 1; x -= x&-x)
        res += b[x];
    return res;
}

int32_t main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], a[i] = abs(a[i])+1;;

    for(int i = 1; i <= n; i++){
        cnt[i] = get(a[i]-1);
        update(a[i], 1);
    }

    memset(b, 0, sizeof b);
    for(int i = n; i >= 1; i--){
        ans += min(cnt[i], get(a[i]-1));
        update(a[i], 1);
    }
    cout << ans;
    return 0;
}