Problem:
 Score : 800 points    Problem Statement You are given a string S consisting of lowercase English letters.
Determine whether we can turn S into a palindrome by repeating the operation of swapping two adjacent characters. If it is possible, find the minimum required number of operations.      Constraints  1 \leq |S| \leq 2 × 10^5  S consists of lowercase English letters.         Input Input is given from Standard Input in the following format:  S       Output If we cannot turn S into a palindrome, print -1 . Otherwise, print the minimum required number of operations.        Sample Input 1 eel      Sample Output 1 1  We can turn S into a palindrome by the following operation:   Swap the 2 -nd and 3 -rd characters. S is now ele .        Sample Input 2 ataatmma      Sample Output 2 4  We can turn S into a palindrome by the following operation:   Swap the 5 -th and 6 -th characters. S is now ataamtma .  Swap the 4 -th and 5 -th characters. S is now atamatma .  Swap the 3 -rd and 4 -th characters. S is now atmaatma .  Swap the 2 -nd and 3 -rd characters. S is now amtaatma .        Sample Input 3 snuke      Sample Output 3 -1  We cannot turn S into a palindrome.

Solution (Python):
from collections import Counter


class fenwick_tree(object):
    def __init__(self, n):
        self.n = n
        self.data = [0] * n

    def __sum(self, r):
        s = 0
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r
        return s

    def add(self, p, x):
        """ a[p] += xを行う"""
        assert 0 <= p and p < self.n
        p += 1
        while p <= self.n:
            self.data[p - 1] += x
            p += p & -p

    def sum(self, l, r):
        """a[l] + a[l+1] + .. + a[r-1]を返す"""
        assert 0 <= l and l <= r and r <= self.n
        return self.__sum(r) - self.__sum(l)


def calc_inversion(arr):
    N = len(arr)
    bit = fenwick_tree(N)
    atoi = {a: i for i, a in enumerate(arr)}
    res = 0
    for a in reversed(range(N)):
        i = atoi[a]
        res += bit.sum(0, i)
        bit.add(i, 1)
    return res


def calc_inv(arr):
    N = len(set(arr))
    atoi = {a: i for i, a in enumerate(sorted(set(arr)))}
    bit = fenwick_tree(N)
    res = 0
    for i, a in enumerate(arr):
        res += i - bit.sum(0, atoi[a] + 1)
        bit.add(atoi[a], 1)
    return res


def main():
    S = input()
    N = len(S)
    C = Counter(S)

    odd = 0
    mid = ""
    for k, v in C.items():
        if v & 1:
            odd += 1
            mid = k

    if N % 2 == 0:  
        if odd:
            return -1
        half = {k: v // 2 for k, v in C.items()}
        cnt = {k: 0 for k in C.keys()}
        label = []
        left = []
        right = []
        for i, s in enumerate(S):
            if cnt[s] < half[s]:
                label.append(0)
                left.append(s)
            else:
                label.append(1)
                right.append(s)
            cnt[s] += 1
        ans = calc_inv(label)

        pos = {k: [] for k in C.keys()}
        for i, s in enumerate(left):
            pos[s].append(i)
        label = []
        for s in right:
            label.append(pos[s].pop())
        ans += calc_inv(label[::-1])
        return ans

    else:  
        if odd != 1:
            return -1
        half = {k: v // 2 for k, v in C.items()}
        cnt = {k: 0 for k in C.keys()}
        label = []
        right = []
        left = []
        seen = 0
        LL = 0  
        RR = 0  

        for i, s in enumerate(S):
            if s == mid and cnt[s] == half[s]:
                seen = 1
                cnt[s] += 1
                continue
            if cnt[s] < half[s]:
                label.append(0)
                left.append(s)
                if seen:
                    LL += 1
            else:
                label.append(1)
                right.append(s)
                if not seen:
                    RR += 1
            cnt[s] += 1
        ans = calc_inv(label)
        ans += RR + LL

        pos = {k: [] for k in C.keys()}
        for i, s in enumerate(left):
            pos[s].append(i)
        label = []
        for s in right:
            label.append(pos[s].pop())
        ans += calc_inv(label[::-1])
        return ans


print(main())

Solution (Python):
"""
まず、奇数個存在する文字種が複数ある場合は、回文にできない。
それ以外の場合は、回文にできる。
次に、操作の最小回数は、回文になった場合の各文字のインデックスを求めておき、BITを使って、入れ替えが必要な回数を求めて置く
"""
from collections import Counter
S = input()
N = len(S)

apperance = Counter(S)


flag = False
for k,v in apperance.items():
    if v%2==1:
        if flag:
            print(-1)
            exit()
        else:
            flag = True
            t = k



place = {}
for i in range(N):
    s = S[i]
    if s not in place:
        place[s] = []
    place[s].append(i)


memo = [-1] *(N)


tmp = 0
tmpApperance = {}
for i in range(N):
    s = S[i]
    if s not in tmpApperance:
        tmpApperance[s] = 1
    else:
        tmpApperance[s] += 1
    if tmpApperance[s] <= apperance[s]//2:
        memo[i] = tmp
        backIdx = place[s][-tmpApperance[s]]
        memo[backIdx] = N-tmp-1
        tmp += 1



if flag:
    idx = N//2
    memo[place[t][len(place[t])//2]] = idx

class BIT:
    def __init__(self,n):
        self.size=n
        self.tree = [0]*(n+1)
    
    def sum(self,i):
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i&-i
        return s
    
    def add(self,i,x):
        while i<=self.size:
            self.tree[i] += x
            i += i&-i
bit = BIT(N)
cnt = 0
for i in range(N):
    m = memo[i]+1
    bit.add(m,1)
    cnt += bit.sum(N)-bit.sum(m)

print(cnt)

Solution (Python):
from collections import Counter

class BIT:
    def __init__(self,n):
        self.tree = [0]*(n+1)
        self.size = n
    
    def sum(self,i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i&-i
        return s

    def add(self,i,x):
        while i <= self.size:
            self.tree[i] += x
            i += i&-i

S = input()
N = len(S)
count = Counter(S)
flag = False
for v in count.values():
    if v%2 == 1:
        if flag:
            print(-1)
            exit()
        else:
            flag = True


"""
文字sのi文字目がどこにあるか、をO(1)で取り出せる辞書が必要
"""
placeAtS = {s:[] for s in list(set(S))}
for i in range(N):
    s = S[i]
    placeAtS[s].append(i)

count2 = {s:0 for s in list(set(S))}

placeAtT = [None]*(N)
tmp = 0
for i in range(N):
    s = S[i]
    count2[s] += 1
    if count2[s] <= count[s]//2:
        placeAtT[i] = tmp
        mirror = placeAtS[s][count[s]-count2[s]]
        placeAtT[mirror] = N - tmp - 1
        tmp += 1

for i in range(N):
    if placeAtT[i] == None:
        placeAtT[i] = tmp

bit = BIT(N)
ans = 0
for i in range(N):
    bit.add(placeAtT[i]+1,1)
    ans += bit.sum(N) - bit.sum(placeAtT[i]+1)

print(ans)

Solution (Python):
"""
回文の左半分の文字列たちを操作する。
左半分の各文字に対して、本来あるべき場所(Index)を定義する。
あとは、左半分の文字

"""

from collections import Counter
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):  
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):  
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

S = input()
N = len(S)
count = Counter(S)


flag = False
for v in count.values():
    if v%2 == 1:
        if flag:
            print(-1)
            exit()
        else:
            flag = True



memo = [None]*(N)

appearCnt = {k:0 for k in count.keys()}


tInd = 0
for i in range(N):
    s = S[i]
    if appearCnt[s] <= count[s]//2 - 1:
        appearCnt[s] += 1
        memo[i] = tInd
        tInd += 1


if flag:
    for i in range(N):
        s = S[i]
        if count[s]%2 == 1 and memo[i]==None:
            memo[i] = tInd
            break



appearIdx = {k:[] for k in count.keys()}
for i in range(N):
    s = S[i]
    appearIdx[s].append(i)

for v in appearIdx.values():
    for i in range(len(v)//2):
        l = v[i]
        r = v[len(v)-i-1]
        memo[r] = (N-1)-memo[l]
ans = 0
bit = BIT(N)
for i in range(N):
    bit.add(memo[i]+1,1)
    ans += bit.sum(N)-bit.sum(memo[i]+1)
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return (int(x) for x in input().split())
def LI(): return list(Is())
def TI(): return tuple(Is())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(S())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18


class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):  
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):  
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    """
    
    bit = BinaryIndexedTree(10)     
    bit.add(2, 10)    
    bit.add(3, -6)    
    print(bit.sum(6)) 
    print(bit.sum(6) - bit.sum(3))  
    """

s = S()
n = len(s)
s_index = defaultdict(list)
for i, x in enumerate(s):
    s_index[x].append(i)

T = [0]*n  
flag = False  
AC = []  
for x, index_list in s_index.items():
    count = len(index_list)
    if count % 2 == 1:
        if flag:
            print(-1)
            exit()
        else:
            flag = True
            mid = index_list[count//2]
            T[mid] = n//2  
    for i in range(count//2):
        a = index_list[i]
        c = index_list[-i-1]
        AC.append((a, c))

AC.sort(key=itemgetter(0))  
for i, (a, c) in enumerate(AC):
    T[a] = i  
    T[c] = n - i - 1

BIT = BinaryIndexedTree(n)
inversion = 0
for i, t in enumerate(T):
    i += 1  
    t += 1  
    BIT.add(t, 1)
    inversion += i - BIT.sum(t)
print(inversion)

Solution (Python):
from collections import deque
alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

S=input()
N=len(S)

dic={moji:deque([]) for moji in alphabetlist}
for i in range(N):
    dic[S[i]].append(i+1)

left=deque([])
right=deque([])
mid=[]

if N%2==1:
    check=0
    memo=0
    for moji in dic:
        if len(dic[moji])%2==1:
            k=len(dic[moji])
            check+=1
            memo=dic[moji][k//2]
    if check!=1:
        print(-1)
        exit()
    else:
        mid.append(memo)
else:
    check=0
    for moji in dic:
        if len(dic[moji])%2==1:
            print(-1)
            exit()

for i in range(N//2):
    for moji in alphabetlist:
        if len(dic[moji])>=2:
            L=dic[moji][0]
            R=dic[moji][-1]
            for moji2 in alphabetlist:
                if len(dic[moji2])>=2 and dic[moji2][0]<L<R<dic[moji2][-1]:
                    break
            else:
                left.append(L)
                right.appendleft(R)
                dic[moji].popleft()
                dic[moji].pop()
                break

ans=list(left)+mid+list(right)
n=N

BIT = [0]*(n+1)


def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum


def BIT_update(idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

res=0
for i in range(N):
    res+=i-BIT_query(ans[i])
    BIT_update(ans[i],1)

print(res)

Solution (Python):
from collections import Counter,defaultdict

class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i

s = input()
n = len(s)
c = Counter(s)
flg = 0
if n%2 == 0:
  for i in c.values():
    if i%2:
      print(-1)
      exit()
else:
  for st,i in c.items():
    if i%2 and flg:
      print(-1)
      exit()
    elif i%2:
      flg = 1
ans = 0
fstr = []
lstr = []
dc = defaultdict(int)
ptr = 0
for i in range(n):
  si = s[i]
  dc[si] += 1
  cnt = dc[si]
  if c[si]%2:
    if cnt*2-1 == c[si]:
      ans += i-ptr
      continue
  if cnt <= c[si]//2:
    ans += i-ptr
    ptr += 1
    fstr.append(si)
  else:
    lstr.append(si)
lstr = lstr[::-1]
n //= 2
perm = [0]*n
fdc = defaultdict(list)
ldc = defaultdict(int)
lcnt = 0
for i in range(n):
  fi = fstr[i]
  fdc[fi].append(i+1)
for i in range(n):
  li = lstr[i]
  perm[i] = fdc[li][ldc[li]]
  ldc[li] += 1
sol = Bit(n+2)
for i in range(n):
  p = perm[i]
  ans += sol.sum(n+1)-sol.sum(p)
  sol.add(p,1)
print(ans)

Solution (Python):
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)
 

def swap_time(array0, array1):
    n = len(array0)
    memo = {}
    for i in range(n)[::-1]:
        if array0[i] not in memo:
            memo[array0[i]] = []
        memo[array0[i]].append(i)
    res = []
    for val in array1:
        ind = memo[val].pop()
        res.append(ind)
    
    bit = BIT(n)
    ans = 0
    for i in range(n):
        bit.add(res[i], 1)
        ans += bit.get_sum(res[i] + 1, n)
    return ans
  
  

ALPH = "abcdefghijklmnopqrstuvwxyz"
s = input()

cnt_memo = {}
for char in s:
    if char not in cnt_memo:
        cnt_memo[char] = 1
    else:
        cnt_memo[char] += 1

odd = ""
for char in cnt_memo:
    if cnt_memo[char] % 2 == 1:
        if odd:
            print(-1)
            exit()
        else:
            odd = char
            cnt_memo[char] -= 1
            cnt_memo[char] //= 2
    else:
        cnt_memo[char] //= 2

left = []
mid = []
if odd:
    mid = [odd]
right = []
for char in s:
    if odd == char and cnt_memo[char] == 0:
        odd = ""
    elif cnt_memo[char] != 0:
        left.append(char)
        cnt_memo[char] -= 1
    else:
        right.append(char)

ans = 0
ans += swap_time(left + mid + right, list(s))
ans += swap_time(left, right[::-1])
print(ans)

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]

class BIT():
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def Sum(self, i):
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def PointAdd(self, i, x):
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

s = input()
n = len(s)
a = [-1 for _ in range(n)]
ch = [[] for _ in range(26)]
for i in range(n):
	ch[ord(s[i])-97].append(i)
if sum([len(x)%2 == 1 for x in ch]) > 1:
	print(-1)
	sys.exit()

for i, c in enumerate(ch):
	tmp = i
	l = len(c)
	for j in range(l//2):
		a[c[j]] = tmp
		a[c[l-j-1]] = tmp
		tmp += 26


former, latter = 0, 0
half = False
d = dict()
cur = 0
bubble = []

ans = 0

for x in a:
	if x >= 0:
		if x not in d:
			d[x] = cur
			cur += 1
			former += 1
			ans += latter + half
		else:
			bubble.append(d[x])
			latter += 1
			if n%2 == 1 and not half:
				ans += 1
	else:
		half = True

bit = BIT(n//2+2)
for b in bubble:
	ans += bit.Sum(b+1)
	bit.PointAdd(b+1, 1)

print(ans)

Solution (Python):
import os
import sys
from collections import Counter


class BinaryIndexedTree:
    
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int i:
        """
        ret = 0
        while i > 0:
            ret += self._bit[i - 1]
            i -= i & -i
        return ret

    def __len__(self):
        return self._size


if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



S = sys.stdin.buffer.readline().decode().rstrip()

counter = Counter(S)

if len(S) % 2 == 0:
    ok = True
    for c, cnt in counter.items():
        ok &= cnt % 2 == 0
else:
    odds = 0
    for c, cnt in counter.items():
        odds += cnt % 2 == 1
    ok = odds == 1
if not ok:
    print(-1)
    exit()



counts = [0] * 26
ls = []
mid = []
rs = []
invs = 0
for c in S:
    n = ord(c) - ord('a')
    counts[n] += 1
    if counter[c] & 1:
        if counts[n] <= counter[c] // 2:
            ls.append(c)
            invs += len(rs) + len(mid)
        elif counts[n] == counter[c] // 2 + 1:
            mid.append(c)
            invs += len(rs)
        else:
            rs.append(c)
    else:
        if counts[n] <= counter[c] // 2:
            ls.append(c)
            invs += len(rs) + len(mid)
        else:
            rs.append(c)

rs = rs[::-1]

l_idx = [[] for _ in range(26)]
for i, c in enumerate(ls):
    n = ord(c) - ord('a')
    l_idx[n].append(i)
counts = [0] * 26
idx = []
for i, c in enumerate(rs):
    n = ord(c) - ord('a')
    idx.append(l_idx[n][counts[n]])
    counts[n] += 1


invs2 = 0
bit = BinaryIndexedTree(size=len(ls))
for i in reversed(idx):
    invs2 += bit.sum(i)
    bit.add(i, 1)
ans = invs + invs2



print(ans)

Solution (Python):
import os
import sys
from collections import Counter


class BinaryIndexedTree:
    
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int i:
        """
        ret = 0
        while i > 0:
            ret += self._bit[i - 1]
            i -= i & -i
        return ret

    def __len__(self):
        return self._size


if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


S = sys.stdin.buffer.readline().decode().rstrip()

counter = Counter(S)

if len(S) % 2 == 0:
    ok = True
    for c, cnt in counter.items():
        ok &= cnt % 2 == 0
else:
    odds = 0
    for c, cnt in counter.items():
        odds += cnt % 2 == 1
    ok = odds == 1
if not ok:
    print(-1)
    exit()



counts = [0] * 26
ls = ''
mid = ''
rs = ''
invs = 0
for c in S:
    n = ord(c) - ord('a')
    counts[n] += 1
    if counter[c] & 1:
        if counts[n] <= counter[c] // 2:
            ls += c
            invs += len(rs) + len(mid)
        elif counts[n] == counter[c] // 2 + 1:
            mid += c
            invs += len(rs)
        else:
            rs += c
    else:
        if counts[n] <= counter[c] // 2:
            ls += c
            invs += len(rs) + len(mid)
        else:
            rs += c

rs = rs[::-1]

l_idx = [[] for _ in range(26)]
for i, c in enumerate(ls):
    n = ord(c) - ord('a')
    l_idx[n].append(i)
counts = [0] * 26
idx = []
for i, c in enumerate(rs):
    n = ord(c) - ord('a')
    idx.append(l_idx[n][counts[n]])
    counts[n] += 1


invs2 = 0
bit = BinaryIndexedTree(size=len(ls))
for i in reversed(idx):
    invs2 += bit.sum(i)
    bit.add(i, 1)
ans = invs + invs2



print(ans)

Solution (Python):
from collections import Counter
S = input()
N = len(S)
ctr = Counter(S)
if len([1 for v in ctr.values() if v%2]) > 1:
    print(-1)
    exit()

M = None
for k,v in ctr.items():
    if v%2:
        M = k
    ctr[k] //= 2

def ctoi(c):
    return ord(c) - ord('a')
from collections import deque
idxs = [deque() for _ in range(26)]
for i,c in enumerate(S):
    idxs[ctoi(c)].append(i)

A = ''
P = []
i = 0
while len(A) < N//2:
    c = S[i]
    if ctr[c] > 0:
        ctr[c] -= 1
        A += c
        P.append(idxs[ctoi(c)].popleft())
    i += 1
if M:
    P.append(idxs[ctoi(M)].popleft())
for c in A[::-1]:
    P.append(idxs[ctoi(c)].popleft())

def inversion(inds):
    bit = [0] * (N+1)
    def bit_add(x,w):
        while x <= N:
            bit[x] += w
            x += (x & -x)
    def bit_sum(x):
        ret = 0
        while x > 0:
            ret += bit[x]
            x -= (x & -x)
        return ret
    inv = 0
    for ind in reversed(inds):
        inv += bit_sum(ind + 1)
        bit_add(ind + 1, 1)
    return inv

print(inversion(P))

Solution (Python):
"""
どれとペアになるかは最初から確定
位置を決めれば後は転倒数
"""
import sys

def bitadd(a,w,bit): 
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): 
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret


S = input()

dic = {}

for i,s in enumerate(S):

    if s not in dic:

        dic[s] = []

    dic[s].append(i)

pair = [None] * len(S)
lis = [None] * len(S)

for i in dic:

    for j in range(len(dic[i]) // 2):

        pair[dic[i][j]] = dic[i][-1-j]
        pair[dic[i][-1-j]] = -1

numnone = 0
for i in pair:
    if i == None:
        numnone += 1

if numnone > 1:
    print (-1)
    sys.exit()

nmax = 0
for i,num in enumerate(pair):

    if num == None:
        lis[i] = len(S)//2

    if num != None and num >= 0:
        
        lis[i] = nmax
        lis[num] = len(S)-1-nmax
        nmax += 1

BIT = [0] * (len(S)+1)
ans = 0
lis.reverse()

for i,num in enumerate(lis):

    num += 1
    ans += bitsum(num,BIT)
    bitadd(num,1,BIT)

print (ans)

Solution (Python):
from collections import Counter


class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


def min_swap_times(s, t):
    if Counter(s) != Counter(t):
        return -1

    n = len(s)
    memo = {}
    for i in range(n):
        if s[i] not in memo:
            memo[s[i]] = [i]
        else:
            memo[s[i]].append(i)
    for i in memo:
        memo[i] = memo[i][::-1]

    array = [0] * n
    for i in range(n):
        array[i] = memo[t[i]][-1]
        del(memo[t[i]][-1])    

    memo = {}
    for i in range(n):
        memo[i] = array[i]
    bit = BIT(n)
    res = 0

    for i in range(n):
        bit.add(memo[i], 1)
        res += bit.get_sum(memo[i] + 1, n)
    return res


import copy

s = input()
n = len(s)
memo = {}
for i in range(n):
    if s[i] not in memo:
        memo[s[i]] = 1
    else:
        memo[s[i]] += 1

odd_cnt = 0
for i in memo:
    odd_cnt += memo[i] % 2
if odd_cnt > 1:
    print(-1)
    exit()

left = []
right = []

memo2 = copy.deepcopy(memo)
ans_cnt = 0
word = ""
for i in range(n):
    if memo2[s[i]]*2 > memo[s[i]] + 1:
        memo2[s[i]] -= 1
        ans_cnt += i - len(left)
        left.append(s[i])
    elif memo2[s[i]]*2 == memo[s[i]] + 1:
        word = s[i]
        memo2[s[i]] -= 1
        right.append(s[i])
    else:
        memo2[s[i]] -= 1
        right.append(s[i])
 
if word != "":
    for i in range(len(right)):
        if right[i] == word:
            ans_cnt += i
            del(right[i])
            break
right = right[::-1]
tmp = min_swap_times(left, right)
if tmp == -1:
    print(-1)
else:
    print(ans_cnt + tmp)

Solution (Python):

class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


import copy

s = input()
n = len(s)
memo = {}
for i in range(n):
    if s[i] not in memo:
        memo[s[i]] = 1
    else:
        memo[s[i]] += 1

odd_cnt = 0
for i in memo:
    odd_cnt += memo[i] % 2
if odd_cnt > 1:
    print(-1)
    exit()

left = []
right = []

memo2 = copy.deepcopy(memo)
ans_cnt = 0
word = ""
for i in range(n):
    if memo2[s[i]]*2 > memo[s[i]] + 1:
        memo2[s[i]] -= 1
        ans_cnt += i - len(left)
        left.append(s[i])
    elif memo2[s[i]]*2 == memo[s[i]] + 1:
        word = s[i]
        memo2[s[i]] -= 1
        right.append(s[i])
    else:
        memo2[s[i]] -= 1
        right.append(s[i])
 
if word != "":
    for i in range(len(right)):
        if right[i] == word:
            ans_cnt += i
            del(right[i])
            break
right = right[::-1]

memo = {}
for i in range(len(right)):
    if right[i] not in memo:
        memo[right[i]] = [i]
    else:
        memo[right[i]].append(i)
for i in memo:
    memo[i] = memo[i][::-1]

for i in range(len(left)):
    tmp = left[i]
    left[i] = memo[tmp][-1]
    del(memo[tmp][-1])

memo = {}
for i in range(len(left)):
    memo[i] = left[i]

bit = BIT(len(left))
for i in range(len(left)):
    bit.add(memo[i], 1)
    ans_cnt += bit.get_sum(memo[i] + 1, len(left))
print(ans_cnt)

Solution (Python):
s = input()
cnt = [0] * 26
n = len(s)

for c in s:
    cnt[ord(c) - ord('a')] += 1

odd = -1
for i in range(26):
    if cnt[i] % 2 == 1:
        if odd != -1:
            print(-1)
            exit()
        odd = i

cnt2 = [[] for i in range(26)]
nums = []
left = 0
for i in range(len(s)):
    c = s[i]
    ind = ord(c) - ord('a')
    if len(cnt2[ind]) * 2 + 1 == cnt[ind]:
        cnt2[ind].append((n-1)//2)
        nums.append((n-1)//2)
    elif len(cnt2[ind]) <= (cnt[ind]-1)//2:
        cnt2[ind].append(left)
        nums.append(left)
        left += 1
    else:
        num = n - 1 - cnt2[ind][cnt[ind]-1-len(cnt2[ind])]
        cnt2[ind].append(num)
        nums.append(num)

ans = 0

bit = [0] * (n+1)
def add(x):
    global bit
    x += 1
    while x <= n:
        bit[x] += 1
        x += x & -x

def sum(x):
    x += 1
    res = 0
    while x:
        res += bit[x]
        x -= x & -x
    return res
for num in nums[::-1]:
    ans += sum(num)
    add(num)

print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque



S = [None] + [int(x) - ord('a') for x in read().rstrip()]

class BinaryIndexedTree():
    def __init__(self, seq):
        self.size = len(seq)
        self.depth = self.size.bit_length()
        self.build(seq)
        
    def build(self,seq):
        data = seq
        size = self.size
        for i,x in enumerate(data):
            j = i+(i&(-i))
            if j < size:
                data[j] += data[i]
        self.data = data
        
    def __repr__(self):
        return self.data.__repr__()
        
    def get_sum(self,i):
        data = self.data
        s = 0
        while i:
            s += data[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        data = self.data
        size = self.size
        while i < size:
            data[i] += x
            i += i & -i
    
    def find_kth_element(self,k):
        data = self.data; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + data[y]
            if sy < k:
                x,sx = y,sy
        return x + 1

N = len(S) - 1
close = [False] * (N+1)

x_to_I = [deque() for _ in range(26)]
for i,x in enumerate(S[1:],1):
    x_to_I[x].append(i)

counter = [len(I) for I in x_to_I]
odd_cnt = sum(x&1 for x in counter)
if odd_cnt >= 2:
    print(-1)
    exit()

find_center = False
bit = BinaryIndexedTree([0] * (N+1))

answer = 0
for r in range(N,0,-1):
    x = S[r]
    bl = close[r]
    if bl:
        continue
    l = x_to_I[x][0]
    if l == r:
        find_center = True
        continue
    x_to_I[x].pop()
    x_to_I[x].popleft()
    costR = 1 if find_center else 0
    costL = l - 1 - bit.get_sum(l)
    bit.add(l,1)
    bit.add(r,1)
    close[l] = True
    answer += costL + costR

print(answer)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

class BitSum:
    def __init__(self, n):
        self.n = n + 3
        self.table = [0] * (self.n + 1)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

def InversionNumber(lst):
    bit = BitSum(max(lst))
    res = 0
    for i, a in enumerate(lst):
        res += i - bit.sum(a)
        bit.update(a, 1)
    return res

def main():
    s = input()
    n = len(s)
    ord_a = ord("a")
    cnts = [0] * 26
    s_code = []
    flag_odd = False
    for c in s:
        code = ord(c) - ord_a
        s_code.append(code)
        cnts[code] += 1
    odd_code = -1
    for code, cnt in enumerate(cnts):
        if cnt % 2 == 1:
            if flag_odd:
                print(-1)
                exit()
            else:
                odd_code = code
                flag_odd = True
        cnts[code] = cnt // 2
    tois = [[] for _ in range(26)]
    to_sort_idx = []
    new_idx = 1
    for code in s_code:
        if cnts[code] > 0:
            to_sort_idx.append(new_idx)
            tois[code].append(n + 1 - new_idx)
            cnts[code] -= 1
            new_idx += 1
        else:
            if flag_odd and code == odd_code:
                to_sort_idx.append(n // 2 + 1)
                flag_odd = False
            else:
                to_sort_idx.append(tois[code].pop())
    
    print(InversionNumber(to_sort_idx))

main()