<commit_before>---
layout: post
title: "転倒数・反転数"
date: 2021-05-31
excerpt: "転倒数・反転数について"
computer_science: true
hide_from_post: true
tag: ["algorithm", "math", "転倒数", "反転数"]
comments: false
---

# 転倒数・反転数について

連続する整数を何回入れ替えると(=バブルソートすると)昇順に並ぶのかをカウントする  

bidを用いたdpのようなことをして計算量を`O(n^2)`から`O(n log n)`にする  

## 基本的な考え方

数字をbitで表現すると大小を少ない回数(ビットのフラグだけ)の操作で、ある値以上、ある値以下の出現回数のdpを作成することができる  

`k`という数字をシフトするのに`k + (k & -k)`という操作を用いる  

具体的な挙動のイメージを掴むのに[google colab](https://colab.research.google.com/drive/16BlTkjAwajxSRW_K6QnFHetP-nUy2AsT?usp=sharing)を用意した  

## pythonでの実装例

```python
N = 6
A = [2,1,3,5,4,6]

class BIT:
    def __init__(self, N):
        self.data = [0]*(N+1)
    def add(self, k, x):
        data = self.data
        while k <= N:
            data[k] += x
            k += k & -k
    def get(self, k):
        data = self.data
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s
b = BIT(N=N)

ans = 0
for i, a in enumerate(A):
    # 自分より小さい要素がいくつ存在するかを計算
    ans += (N-1-i) - b.get(a)
    b.add(a, 1)
print(ans) # 2
```

## 参考
 - [反転数](https://tjkendev.github.io/procon-library/python/sequence/number_of_inversions.html)

## 例; 半点数を普通に求めたあと、リストの操作を一般化する例
**問題**  
[AtCoder Beginner Contest 190; F - Shift and Inversions](https://atcoder.jp/contests/abc190/tasks/abc190_f)

**解説**  
先頭から要素を削除するコストと、後ろに要素を追加するコストの差を見ることで一般か可能  

**解答**  
```python
N=int(input())
*A,=map(lambda x:int(x)+1, input().split())

class BIT:
    def __init__(self, N):
        self.data = [0]*(N+1)
    def add(self, k, x):
        data = self.data
        while k <= N:
            data[k] += x
            k += k & -k
    def get(self, k):
        data = self.data
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s
b = BIT(N=N)

ans = 0<commit_msg>fix typo of "-転倒数-反転数"<commit_after>---
layout: post
title: "転倒数・反転数"
date: 2021-05-31
excerpt: "転倒数・反転数について"
computer_science: true
hide_from_post: true
tag: ["algorithm", "math", "転倒数", "反転数"]
comments: false
---

# 転倒数・反転数について

連続する整数を何回入れ替えると(=バブルソートすると)昇順に並ぶのかをカウントする  

bidを用いたdpのようなことをして計算量を`O(n^2)`から`O(n log n)`にする  

## 基本的な考え方

数字をbitで表現すると大小を少ない回数(ビットのフラグだけ)の操作で、ある値以上、ある値以下の出現回数のdpを作成することができる  

`k`という数字をシフトするのに`k + (k & -k)`という操作を用いる  

具体的な挙動のイメージを掴むのに[google colab](https://colab.research.google.com/drive/16BlTkjAwajxSRW_K6QnFHetP-nUy2AsT?usp=sharing)を用意した  

## pythonでの実装例

```python
N = 6
A = [2,1,3,5,4,6]

class BIT:
    def __init__(self, N):
        self.data = [0]*(N+1)
    def add(self, k, x):
        data = self.data
        while k <= N:
            data[k] += x
            k += k & -k
    def get(self, k):
        data = self.data
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s
b = BIT(N=N)

ans = 0
for i, a in enumerate(A):
    # 自分より小さい要素がいくつ存在するかを計算
    ans += (N-1-i) - b.get(a)
    b.add(a, 1)
print(ans) # 2
```

## 参考
 - [反転数](https://tjkendev.github.io/procon-library/python/sequence/number_of_inversions.html)

## 例; 反転数を普通に求めたあと、リストの操作を一般化する例
**問題**  
[AtCoder Beginner Contest 190; F - Shift and Inversions](https://atcoder.jp/contests/abc190/tasks/abc190_f)

**解説**  
先頭から要素を削除するコストと、後ろに要素を追加するコストの差を見ることで一般化が可能  

**解答**  
```python
N=int(input())
*A,=map(lambda x:int(x)+1, input().split())

class BIT:
    def __init__(self, N):
        self.data = [0]*(N+1)
    def add(self, k, x):
        data = self.data
        while k <= N:
            data[k] += x
            k += k & -k
    def get(self, k):
        data = self.data
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s
b = BIT(N=N)

ans = 0
{'fraction_non_alphanumeric': 0.1625, 'fraction_numerical': 0.022282608695652174, 'mean_word_length': 2.4530956848030017, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 3, 'https://': 6, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3105564', 'n_tokens_mistral': 2046, 'n_tokens_neox': 1938, 'n_words': 310}