Problem:
 Score : 600 points    Problem Statement You are given an integer sequence of length N , a = { a_1, a_2, …, a_N }, and an integer K .  a has N(N+1)/2 non-empty contiguous subsequences, { a_l, a_{l+1}, …, a_r } (1 ≤ l ≤ r ≤ N) . Among them, how many have an arithmetic mean that is greater than or equal to K ?      Constraints  All input values are integers.  1 ≤ N ≤ 2 \times 10^5  1 ≤ K ≤ 10^9  1 ≤ a_i ≤ 10^9         Input Input is given from Standard Input in the following format:  N  K  a_1  a_2  :  a_N       Output Print the number of the non-empty contiguous subsequences with an arithmetic mean that is greater than or equal to K .        Sample Input 1 3 6
7
5
7      Sample Output 1 5  All the non-empty contiguous subsequences of a are listed below:   { a_1 } = { 7 }  { a_1, a_2 } = { 7, 5 }  { a_1, a_2, a_3 } = { 7, 5, 7 }  { a_2 } = { 5 }  { a_2, a_3 } = { 5, 7 }  { a_3 } = { 7 }   Their means are 7 , 6 , 19/3 , 5 , 6 and 7 , respectively, and five among them are 6 or greater. Note that { a_1 } and { a_3 } are indistinguishable by the values of their elements, but we count them individually.       Sample Input 2 1 2
1      Sample Output 2 0       Sample Input 3 7 26
10
20
30
40
30
20
10      Sample Output 3 13

Solution (Python):

class BIT:
  def __init__(self, n):
    self.n = n
    self.bit = [0]*(n+1)
    self.el = [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, x):
    
    self.el[i] += x
    while i <= self.n:
      self.bit[i] += x
      i += i & -i

N, K = map(int, input().split())
A = [int(input())-K for _ in range(N)]
from itertools import groupby, accumulate, product, permutations, combinations
cum = [0]+list(accumulate(A))
comp = lambda arr: {e: i+1 for i, e in enumerate(sorted(set(arr)))}
compcum = comp(cum)
for i in range(N+1):
  cum[i] = compcum[cum[i]]
bit = BIT(N+1)
ans = 0
for i in range(N+1):
  ans += bit.sum(cum[i])
  bit.add(cum[i],1)
print(ans)

Solution (Python):
class Bit:
    def __init__(self, n):
        self.n = n
        self.tree = [0]*(n+1)
        self.el = [0]*(n+1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def add(self, i, x):
        self.el[i] += x
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

class BitSet2:
    """ 座標圧縮が必要な場合 """
    def __init__(self, data, A=[]):
        """ BitSetに入り得る値を先読みした物を data に格納 """
        self.data = sorted(list(set(data)))
        self.n = len(self.data)
        self.p = Bit(self.n + 1)
        self.size = 0
        self.flip = 0
        self.code = {}
        self.decode = {}
        for i, b in enumerate(self.data):
            self.code[b] = i
            self.decode[i] = b
        for a in A:
            self.add(a)

    def add(self,x):
        self.p.add(self.code[x], 1)
        self.size += 1
        self.flip += self.size - self.p.sum(self.code[x]+1)

    def remove(self,x):
        self.p.add(x, -1)
        self.size -= 1

    def flip_counter(self):
        return self.flip





import sys
input = sys.stdin.readline
from itertools import accumulate
N, K = map(int, input().split())
A = []
for _ in range(N):
    A.append(int(input()))
S = [0] + list(accumulate(A))
T = []
for i, s in enumerate(S):
    T.append(s-K*i)
B = BitSet2(T,T)
print(N*(N+1)//2-B.flip_counter())

Solution (Python):
class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,k=map(int,input().split())
arr=[0]+[int(input()) for _ in range(n)]
for i in range(1,n+1):
  arr[i]+=arr[i-1]-k
s=set(arr)
key=sorted(list(s))
dic={}
for i in range(len(key)):
  dic[key[i]]=i+1
bit=BIT(len(key)+1)
ans=0
bit.add(dic[0],1)
for i in range(1,n+1):
  ans+=bit.sum(1,dic[arr[i]])
  bit.add(dic[arr[i]],1)
print(ans)

Solution (Python):
class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,k=map(int,input().split())
arr=[0]+[int(input()) for _ in range(n)]
for i in range(1,n+1):
  arr[i]+=arr[i-1]-k
s=set(arr)
key=sorted(list(s))
dic={}
for i in range(len(key)):
  dic[key[i]]=i+1
bit=BIT(len(key)+1)
ans=0
bit.add(dic[0],1)
for i in range(1,n+1):
  ans+=bit.sum(1,dic[arr[i]])
  bit.add(dic[arr[i]],1)
print(ans)

Solution (Python):
from collections import defaultdict
n, k = map(int, input().split())

a = [int(input()) - k for _ in range(n)]
s = [0] * (n + 1)
for i in range(n):
	s[i + 1] = s[i] + a[i]

mp = defaultdict(int)
b = sorted(list(set(s)))
num = 1
for c in b:
	mp[c] = num
	num += 1
m = len(mp)
d = [0] * (m + 1)

def add(i):
	while i <= m:
		d[i] += 1
		i += i & -i
def qqq(i):
	res = 0
	while i > 0:
		res += d[i]
		i -= i & -i
	return res

ans = 0
for i in range(n + 1):
	ans += qqq(mp[s[i]])
	add(mp[s[i]])
print(ans)

Solution (Python):
from itertools import accumulate
n, k = map(int, input().split())

BIT = [0] * (n + 10)
def add(i, x):
    while i <= (n + 10):
        BIT[i] += x
        i += i & -i
def query(i):
    s = 0
    while i > 0:
        s += BIT[i]
        i -= i & -i
    return s
a = [0] + [int(input()) - k for i in range(n)]
a = list(accumulate(a))
b = sorted(a)
b.append(-float("inf"))
cnt = 0
dic = dict()
for i in range(n + 1):
    if b[i] != b[i - 1]:
        cnt += 1
        dic[b[i]] = cnt
answer = 0
for I in range(n + 1):
    answer += query(dic[a[I]])
    add(dic[a[I]], 1)
print(answer)

Solution (Python):
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)


def main(n,k,a):
  b=[x-k for x in a]
  tmp=0
  cb=[tmp]
  for x in b:
    tmp+=x
    cb.append(tmp)
  from bisect import bisect_right
  cbb=cb.copy()
  cbb.sort()
  cb=[bisect_right(cbb,x) for x in cb]
  bit=BIT(n+2)
  ans=0
  for x in cb:
    ans+=bit.sum(x)
    bit.add(x,1)
  return ans

n,k=map(int,input().split())
a=[int(input()) for _ in range(n)]
print(main(n,k,a))

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N + 1)
        self.b = 1 << N.bit_length() - 1

    
    def add(self, a, w):
        x = a
        while(x <= self.N):
            self.bit[x] += w
            x += x & -x

    
    def get(self, a):
        ret, x = 0, a - 1
        while(x > 0):
            ret += self.bit[x]
            x -= x & -x
        return ret

    def cum(self, l, r):
        return self.get(r) - self.get(l)

    def lowerbound(self, w):
        if w <= 0:
            return 0
        x = 0
        k = self.b
        while k > 0:
            if x + k <= self.N and self.bit[x + k] < w:
                w -= self.bit[x + k]
                x += k
            k //= 2
        return x + 1

N, K = getNM()
A = getArray(N)





















A = [i - K for i in A]
imos = [0]
for i in range(N):
    imos.append(imos[i] + A[i])
mi = min(imos)
imos = [i - mi for i in imos] 
N += 1




def compress(array):
    s = set(array)
    s = sorted(list(s))
    alter = {}
    rev = {}
    for i in range(len(s)):
        alter[s[i]] = i
        rev[i] = s[i]
    return alter, rev

alter, rev = compress(imos)
limit = N + 1
bit = BIT(limit)
ans = 0
for i in range(N):
    
    ans += bit.get(alter[imos[i]] + 2) 
    bit.add(alter[imos[i]] + 1, 1) 

print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N + 1)
        self.b = 1 << N.bit_length() - 1

    
    def add(self, a, w):
        x = a
        while(x <= self.N):
            self.bit[x] += w
            x += x & -x

    
    def get(self, a):
        ret, x = 0, a - 1
        while(x > 0):
            ret += self.bit[x]
            x -= x & -x
        return ret

    def cum(self, l, r):
        return self.get(r) - self.get(l)

    def lowerbound(self, w):
        if w <= 0:
            return 0
        x = 0
        k = self.b
        while k > 0:
            if x + k <= self.N and self.bit[x + k] < w:
                w -= self.bit[x + k]
                x += k
            k //= 2
        return x + 1

N, K = getNM()
A = getArray(N)





















A = [i - K for i in A]
imos = [0]
for i in range(N):
    imos.append(imos[i] + A[i])
mi = min(imos)
imos = [i - mi for i in imos]
N += 1




def compress(array):
    s = set(array)
    s = sorted(list(s))
    alter = {}
    rev = {}
    for i in range(len(s)):
        alter[s[i]] = i
        rev[i] = s[i]
    return alter, rev

alter, rev = compress(imos)
limit = N + 1
bit = BIT(limit)
ans = 0
for i in range(N):
    
    ans += bit.get(alter[imos[i]] + 2)
    bit.add(alter[imos[i]] + 1, 1)

print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
a = [int(input()) for _ in range(n)]
for i in range(n):
    a[i] -= k
def cumsum(a):
    """※ aを破壊する
    l[i] = sum(a[:i]) なるlを返す
    sum(a[i:j]) == l[j+1] - l[i]
    """
    c = 0
    n = len(a)
    a.insert(0, 0)
    for i in range(1, n+1):
        a[i] = a[i-1]+a[i]
    return a
cumsum(a)
l = [a[0]]
ans = 0

def init(bit, values):
    for i,v in enumerate(values):
        add(bit,i+1,v)

def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res


def add(bit,i,x):
    if i==0:
        raise RuntimeError
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return


def index(bit, v):
    i = 0
    k = 1
    n = len(bit)-1
    while 2*k<n:
        k *= 2
    while k>0:
        if i+k<n+1 and bit[i+k]<v:
            v -= bit[i+k]
            i += k
        k //= 2
    return i+1

from bisect import bisect_left
from bisect import bisect_left as bl, bisect_right as br

def press(l):
    
    xs = sorted(set(l))
    inds = [None] * len(l)
    for i,item in enumerate(l):
        inds[i] = bisect_left(xs, item)
    return xs, inds
xs, inds = press(a)
bit = [0]*(len(inds)+1)
ans = 0
num = 0
for i in inds:
    ans += query(bit, i+1)
    add(bit, i+1, 1)

    num += 1
print(ans)

Solution (Python):
n, k = map(int, input().split())
A = [int(input()) for i in range(n)]
A = [a-k for a in A]

from itertools import accumulate
C = [0]+A
C = list(accumulate(C))


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

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

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

    def sum(self, i, j):
        
        return self._sum(j) - self._sum(i)

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

B = list(set(C))
B.sort(reverse=True)
D = {}
for i, b in enumerate(B):
    D[b] = i

C = [D[c] for c in C]
bit = BIT(max(C)+1)
ans = 0
for c in C:
    ans += bit.sum(c, bit.n)
    bit.add(c, 1)
print(ans)

Solution (Python):
n, k = map(int, input().split())
A = [int(input()) for i in range(n)]
A = [a-k for a in A]

from itertools import accumulate
C = [0]+A
C = list(accumulate(C))


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

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

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

    def sum(self, i, j):
        
        return self._sum(j) - self._sum(i)

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

B = list(set(C))
B.sort(reverse=True)
D = {}
for i, b in enumerate(B):
    D[b] = i

C = [D[c] for c in C]
bit = BIT(max(C)+1)
ans = 0
for c in C:
    ans += bit.sum(c, bit.n)
    bit.add(c, 1)
print(ans)

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,K = MI()
A = [0]  
for i in range(N):
    A.append(A[-1]+I()-K)



B = sorted(list(set(A)))
d = {}
for i in range(len(B)):
    d[B[i]] = i+1

for i in range(N+1):
    A[i] = d[A[i]]




class BIT():
    def __init__(self,init_value):
        self.n = len(init_value)
        self.tree = [0]*(self.n+1)
        for i in range(1,self.n+1):
            x = init_value[i-1]
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)
    def update(self,i,x):  
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)
        return
    def query(self,i):  
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & (-i)
        return res


BIT = BIT([0]*(N+1))
ans = 0
for i in range(N+1):
    ans += BIT.query(A[i])
    BIT.update(A[i],1)
print(ans)

Solution (Python):
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class SegmentTree(object):
	
	def __init__(self, N):
		self.N = N
		self.N0 = 2 ** (N - 1).bit_length()
		self.initVal = 0
		self.data = [self.initVal] * (2 * self.N0)

	
	def calc(self, a, b):
		return a + b

	
	def add(self, k, x):
		k += self.N0 - 1
		self.data[k] += x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = self.calc(self.data[2 * k + 1], self.data[2 * k + 2])

	
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				m = self.calc(m, self.data[R - 1])
			if L & 1:
				m = self.calc(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return m


def main():
	N, K = getlist()
	A = []
	for i in range(N):
		a = int(input())
		A.append(a)

	
	for i in range(N):
		A[i] -= K
	
	
	B = [0]
	for i in range(N):
		B.append(B[-1] + A[i])

	
	C = list(set(B))
	C.sort()
	D = defaultdict(int)
	for i in range(len(C)):
		D[C[i]] = i

	
	for i in range(N + 1):
		B[i] = D[B[i]]

	
	ans = 0
	Seg = SegmentTree(N + 1)
	for i in range(N + 1):
		b = B[i]
		val = Seg.query(0, b)
		ans += val
		Seg.add(b, 1)

	print(ans)


if __name__ == '__main__':
	main()

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

    def get_sum(self, i=None):
        if i is None:
            i = self.size
        m = 0  
        while i > 0:
            m += self.tree[i]
            i -= i & -i
        return m

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

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
X = [0]*N
X[0] = A[0]-K
for i in range(1,N):
    X[i] = X[i-1] + A[i] - K

Y = sorted(set(X))
dic = {y:i+1 for i,y in enumerate(Y)}

BIT = Sum_Bit(N)
ans = 0
for i in range(N):
    ans += BIT.get_sum(dic[X[i]])
    if X[i] >= 0: ans += 1
    BIT.update(dic[X[i]], 1)
    
print(ans)

Solution (Python):
class BIT: 
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length()
        self.n0 = 1<<self.depth

    def get_sum(self, i): 
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def query(self,l,r): 
        return self.get_sum(r) - self.get_sum(l-1) 
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        
    
    def bisect_left(self,w):
        
        
        if w <= 0: return 0
        x,k = 0,self.n0
        for _ in range(self.depth):
            k >>= 1
            if x+k <= self.size and self.tree[x+k] < w:
                w -= self.tree[x+k]
                x += k
        return x
    



import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,k,*a = map(int,read().split())
b = [0]+[k-i for i in a]


from itertools import accumulate
sa = sorted(set(accumulate(b)))

zaatu = {ai:i for i,ai in enumerate(sa)}

v = 0
bit = BIT(n+1)

ans = 0
for i,ai in enumerate(a):
    ai -= k
    bit.add(zaatu[-v],1)    
    v += ai
    idx = zaatu[-v]
    
    res = i+1
    if idx: res -= bit.get_sum(idx-1)
    ans += res




print(ans)

Solution (Python):
from bisect import bisect_left
class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*N
    def add(self,a,w):
        x=a
        while(x<self.N):
            self.bit[x]+=w
            x|=x+1
    def get(self,a):
        ret,x=0,a-1
        while(x>=0):
            ret+=self.bit[x]
            x=(x&(x+1))-1
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l)

N,K=map(int,input().split())
a=[int(input()) for i in range(N)]
cum=[0]*(N+1)
for i in range(N):
    cum[i+1]=cum[i]+a[i]
B=[cum[i]-i*K for i in range(N+1)]

dic={}
li=sorted(B)
for i in range(N+1):
    dic[B[i]]=bisect_left(li,B[i])
bit=BIT(N+1)
ans=0
for i in range(N+1):
    ans+=bit.get(dic[B[i]]+1)
    bit.add(dic[B[i]],1)
print(ans)

Solution (Python):
from bisect import bisect_left
class SEGTree:
    def __init__(self,n):
        self.Unit=0
        i=1
        while(i<n):
            i*=2
        self.SEG=[self.Unit]*(2*i-1)
        self.d=i
    def update(self,i,x):
        i+=self.d-1
        self.SEG[i]+=x
        while i>0:
            i=(i-1)//2
            self.SEG[i]=self.SEG[i*2+1]+self.SEG[i*2+2]
    def find(self,a,b,k,l,r):
        if r<=a or b<=l:
            return self.Unit
        if a<=l and r<=b:
            return self.SEG[k]
        else:
            c1=self.find(a,b,2*k+1,l,(l+r)//2)
            c2=self.find(a,b,2*k+2,(l+r)//2,r)
            return c1+c2
    def get(self,a,b):
        return self.find(a,b,0,0,self.d)
N,K=map(int,input().split())
a=[int(input()) for i in range(N)]
cum=[0]*(N+1)
for i in range(N):
    cum[i+1]=cum[i]+a[i]
B=[cum[i]-i*K for i in range(N+1)]

dic={}
li=sorted(B)
for i in range(N+1):
    dic[B[i]]=bisect_left(li,B[i])
seg=SEGTree(N+1)
ans=0
for i in range(N+1):
    ans+=seg.get(0,dic[B[i]]+1)
    seg.update(dic[B[i]],1)
print(ans)

Solution (Python):
import bisect

def make_tree(n):
    i = 2
    while True:
        if i >= n * 2:
            tree = [0] * i
            break
        else:
            i *= 2
    return tree

def update(i, x):
    i += len(tree) // 2
    tree[i] = x
    i //= 2
    while True:
        if i == 0:
            break
        tree[i] = tree[2 * i] + tree[2 * i + 1]
        i //= 2
    return

def find(s, t):
    s += len(tree) // 2
    t += len(tree) // 2
    ans = 0
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            ans += tree[s]
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans += tree[t]
            t = (t - 1) // 2
    return ans

n, k = map(int, input().split())
a = [int(input()) for _ in range(n)]
s = [0] * (n + 1)
for i in range(n):
    s[i + 1] += s[i] + a[i]
for i in range(n + 1):
    s[i] -= k * i
d = dict()
for i in s:
    if not i in d:
        d[i] = 1
    else:
        d[i] += 1
x = list(d.keys())
x.sort()
tree = make_tree(len(x))
for i in range(len(x)):
    update(i, d[x[i]])
cnt = 0
l = len(tree) // 2
for i in s:
    b = bisect.bisect_left(x, i)
    update(b, tree[l + b] - 1)
    cnt += find(b, l - 1)
print(cnt)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

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



n, k = LI()
A  = IR(n)
A = [0] + list(accumulate([a - k for a in A]))
D  = {v:i for i,v in enumerate(sorted(A))}
bit = BIT(len(A))
c = 0
for a in A:
    c += bit.sum(D[a])
    bit.add(D[a], 1)

print(c)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

from itertools import permutations,product,combinations_with_replacement,groupby,accumulate,combinations
class BinaryIndexedTree():
    def __init__(self,N):
        self.N = N
        self.tree = [0] * (N + 1)
    
    def add(self,i,x):
        while i <= self.N:
            self.tree[i] += x
            i += (i & -i)
    
    def sum(self,i):
        ret = 0
        while i > 0:
            ret += self.tree[i]
            i -= (i & -i)
        return ret
    
    def lower_bound(self,x):
        if x <= 0:
            return 0
        i = 0
        K = 1 << self.N.bit_length()
        while K > 0:
            if i + K <= self.N and self.tree[i + K] < x:
                x -= self.tree[i + K]
                i += K
            K >>= 1
        return i + 1
    
    def __str__(self):
        return ' '.join(map(str,self.tree))

def main():
    N,K = map(int,input().split())
    A = [int(input()) for _ in range(N)]
    A = [0] + [a - K for a in A]
    A = list(accumulate(A))

    compress = list(sorted(set(A)))
    dic = {c:i for i,c in enumerate(compress,1)}
    bit = BinaryIndexedTree(len(compress))
    ans = N*(N + 1)//2
    for i,a in enumerate(A):
        j = dic[a]
        ans -= i - bit.sum(j)
        bit.add(j,1)
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
n,k=map(int,input().split())
a=[int(input())for i in range(n)]
from itertools import accumulate
l=[0]+list(accumulate(a))
l=[j-k*i for i,j in enumerate(l)]


a_to_i={a:i for i,a in enumerate(sorted(set(l)),1)}
b=[a_to_i[a]for a in l]

size=len(a_to_i)+2
bit=[0]*size



def bit_update(x,v):
    while x<size:
        bit[x]+=v
        x+=(x&-x) 


def bit_sum(n):
    s=0
    if n==0:return 0
    x=n
    while x>0:
        s+=bit[x]
        x-=(x&-x)
    return s

ans=0
for i in b:
    ans+=bit_sum(i)
    bit_update(i,1)
print(ans)

Solution (Python):

N, K = map(int, input().split())
d = []
for _ in range(N):
    a = int(input())
    d.append(a-K)
b = [0 for i in range(N)]
b[0] = [d[0], 0]
for i in range(1, N):
    d[i] += d[i-1]
    b[i] = [d[i], i]
rev = 0
for i in range(N):
    if d[i] < 0:
        rev += 1
para = 1

b.sort()

b[0][0] = para

for i in range(1, N):
    now = b[i-1][1]
    next_ = b[i][1]
    if d[now] == d[next_]:
        b[i][0] = para
    else:
        para += 1
        b[i][0] = para
b.sort(key=lambda x: x[1])
for i in range(N):
    d[i] = b[i][0]




ans = N*(N+1)//2



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

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

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

    def get(self, i, j):
        return self.to_sum(j)-self.to_sum(i-1)


ans = N*(N+1)//2

tree = BIT(N+1)

for index, p in enumerate(d):
    tree.add(p, 1)
    rev += index+1-tree.to_sum(p)
    
ans -= rev
print(ans)

Solution (Python):
import copy

class BinaryIndexedTree():
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
 
    def initialize(self, seq):
        for i, x in enumerate(seq[1:], 1):
            self.tree[i] += x
            j = i + (i & (-i))
            if j < self.size:
                self.tree[j] += self.tree[i]
 
    def __repr__(self):
        return self.tree.__repr__()
 
    def get_sum(self, i):
        s = 0
        while i:
            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
 
    def find_kth_element(self, k):
        x, sx = 0, 0
        dx = (1 << self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= self.size:
                continue
            y = x + dx
            sy = sx + self.tree[y]
            if sy < k:
                x, sx = y, sy
        return x + 1

n,k = map(int,input().split())
a = [int(input()) for _ in range(n)]
ssum = [0]*(n+1)
for i in range(1,n+1):
    ssum[i] = ssum[i-1] + a[i-1]

r = [0]*(n+1)
for i in range(n+1):
    r[i] = ssum[i]-i*k

r2 = copy.copy(r)
r2.sort()

d = dict()
cnt = 1
d[r2[0]] = 1
for i in range(1,n+1):
    if r2[i] != r2[i-1]:
        cnt += 1
    d[r2[i]] = cnt


bit = BinaryIndexedTree(2*10**5+5)
ans = 0

for i in range(n,-1,-1):
    t = d[r[i]]
    ans += bit.get_sum(2*10**5+2)-bit.get_sum(t-1)
    bit.add(t, 1)

print(ans)