セグメント木、BIT（反転数）

・セグメント木
書きようによっては任意の区間のGCDを求めたりもできるっぽいけど、とりあえずは任意の区間の最小値を求めることにする。

n = int(input()) #配列の要素数をnと置く。
L = list(map(int,input().split())) #配列
t = 1
while t <= n:
    t *= 2
segtree = [float('inf')]*(t-1) #tはn以上で最小の2のべき乗の数

def init(LIST):
    for i in range(n):
        segtree[i+n-1] = LIST[i] #配列のi番目をセグ木のi+n-1番目（葉）に格納
    for i in range(n-2, -1, -1):
        segtree[i] = min(segtree[2*i+1], segtree[2*i+2])

def update(k, a): #k番目（0-indexed）の値をaに変更
    k += n-1
    segtree[k] = a
    while k > 0:
        k = (k-1)//2
        segtree[k] = min(segtree[2*k+1], segtree[2*k+2])

def query(a, b, k, l, r): #[L[a],L[b])の範囲の最小値を求める。kは今見ている節点の番号、l,rはkの対応している範囲を表す。
#L[a]~L[b]の最小値を求めたければ、query(a,b+1,0,0,n)
    if r <= a or b <= l: #求める場所が範囲外
        return float('inf')
    elif a <= l and r <= b:
        return segtree[k]
    else:
        u = query(a, b, 2*k+1, l, (l+r)//2)
        v = query(a, b, 2*k+2, (l+r)//2, r)
        return min(u, v)
        
init(L)
print(segtree)
while True:
    i,p,q = map(int,input().split()) #i==1でL[p]~L[q]のminを求める。i==2でL[p]をqに変更
    if i == 1:
        print(query(p, q+1, 0, 0, n))
    elif i == 2:
        update(p, q)
        print(segtree)
    else:
        break

実行例

>>8
>>5 3 7 9 6 4 1 2
[1, 3, 1, 3, 7, 4, 1, 5, 3, 7, 9, 6, 4, 1, 2]
>>2 0 2 #L[0]を5から2に変更
[1, 2, 1, 2, 7, 4, 1, 2, 3, 7, 9, 6, 4, 1, 2]
>>1 0 0 #L[0]の値
2
>>1 0 3 #L[0]~L[3]の最小値
2
>>1 0 7 #L[0]~L[7]の最小値
1
>> 1 4 3 #範囲が前後する
inf

・BIT
任意の区間の和を求めることができる嬉しい配列。

n = int(input()) #配列の要素数をnと置く。
L = list(map(int,input().split())) #配列
BIT = [0]*(n+1) #1-indexed
def sum_1_to_i(i): #L[1]~L[i]の和を求める
    ans = 0
    while i > 0:
        ans += BIT[i]
        i -= i & -i #ビットが立っている最下位の桁を0に
    return ans

def update(i, x): #L[i]にxを加算する
    while i <= n:
        BIT[i] += x
        i += i & -i
    return

for i in range(n):
    update(i+1, L[i])
print(BIT)

while True:
    i,p,q = map(int,input().split())
    if i == 1:
        print(sum_1_to_i(q)-sum_1_to_i(p))
    else:
        break

実行例

6 
1 2 3 4 5 6
[0, 1, 3, 3, 10, 5, 11]
>>1 3 6 #4+5+6
15
>>1 2 6 #3+4+5+6
18
>>1 0 3 #1+2+3
6
>>1 0 6
21

・1~nを適当に並べた配列における反転数（バブルソートの回数）を求めるコード
※反転数＝バブルソートの回数なのは、①一回の入れ替えで反転数は-1、②昇順に並んでる時の反転数は0、の二つから従う。

n = int(input()) #配列の要素数をnと置く。
L = list(map(int,input().split())) #配列
BIT = [0]*(n+1) #1-indexed
def sum_1_to_i(i): #L[1]~L[i]の和を求める
    ans = 0
    while i > 0:
        ans += BIT[i]
        i -= i & -i #ビットが立っている最下位の桁を0に
    return ans

def update(i, x): #L[i]にxを加算する
    while i <= n:
        BIT[i] += x
        i += i & -i
    return

times_of_swap = 0

for i in range(n):
    times_of_swap += i-sum_1_to_i(L[i])
    update(L[i], 1)
print(times_of_swap)

参考：
転倒数 - 個人的な競プロメモ