Submission #72539097

---

Source Code Expand

N=int(input())
S=list(input())
D=[0]
for i in range(N) :
    if S[i]=="A" :
        D.append(D[-1]-1000000+1)
    elif S[i]=="B" :
        D.append(D[-1]+1000000+1)
    else :
        D.append(D[-1]+1)
class BIT:
    def __init__(self, N):
        self.N = N
        self.bits = [0] * (self.N + 1)
        
    def update(self, i, x):
        while i <= self.N:
            self.bits[i] += x
            i += i & -i
    
    def total(self, i):
        res = 0
        
        while i > 0:
            res += self.bits[i]
            i -= i & -i
            
        return res
def binary_search(data, value):
    left = 0            # 探索する範囲の左端を設定
    right = len(data) - 1            # 探索する範囲の右端を設定
    while left <= right:
        mid = (left + right) // 2            # 探索する範囲の中央を計算
        if data[mid] == value:
            # 中央の値と一致した場合は位置を返す
            return mid
        elif data[mid] < value:
            # 中央の値より大きい場合は探索範囲の左を変える
            left = mid + 1
        else:
            # 中央の値より小さい場合は探索範囲の右を変える
            right = mid - 1
    return -1            # 見つからなかった場合
#これは事故らない二分探索です
def binary_min(data, lower_bound):
    value=lower_bound
    left = 0            # 探索する範囲の左端を設定
    right = len(data) - 1            # 探索する範囲の右端を設定
    while left < right:
        mid = (left + right) // 2# 探索する範囲の中央を計算
        if data[mid] < value:
            # 中央の値より大きい場合は探索範囲の左を変える
            left = mid +1
        else:
            # 中央の値より小さい場合は探索範囲の右を変える
            right = mid
    mid = (left + right) // 2
    return mid            # 見つからなかった場合
#これは事故らない二分探索です
def binary_max(data, upper_bound):
    value=upper_bound
    left = 0            # 探索する範囲の左端を設定
    right = len(data) - 1            # 探索する範囲の右端を設定
    while left < right:
        mid = (left + right+1) // 2# 探索する範囲の中央を計算
        if data[mid] > value:
            # 中央の値より大きい場合は探索範囲の左を変える
            right = mid -1
        else:
            # 中央の値より小さい場合は探索範囲の右を変える
            left = mid
    mid = (left + right) // 2
    return mid            # 見つからなかった場合
def compression(data) :
    V=data.copy()
    V=sorted(V)
    last="^o^"
    E=[]
    F=[]
    for i in range(len(V)):
        if V[i]!=last :
            E.append(V[i])
        last=V[i]
    for i in range(len(V)) :
        F.append(binary_search(E,data[i]))
    return  F
N +=1
bits = BIT(N)
S = sorted(list(set(D)))
ranking = {x:i+1 for i,x in enumerate(S)}
E = []
for a in D:
  E.append(ranking[a])

count = 0

for i in range(N - 1, -1, -1):
    count += bits.total(E[i] - 1)
    bits.update(E[i], 1)
print(count)

Submission Info

Judge Result