Problem:


Score : 400 points

Problem Statement

We have N balls. The i-th ball has an integer A_i written on it.

For each k=1, 2, ..., N, solve the following problem and print the answer.  

Find the number of ways to choose two distinct balls (disregarding order) from the N-1 balls other than the k-th ball so that the integers written on them are equal.

Constraints

3 \leq N \leq 2 \times 10^5

1 \leq A_i \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

For each k=1,2,...,N, print a line containing the answer.

Sample Input 1

5
1 1 2 1 2

Sample Output 1

2
2
3
2
3

Consider the case k=1 for example. The numbers written on the remaining balls are 1,2,1,2.

From these balls, there are two ways to choose two distinct balls so that the integers written on them are equal.

Thus, the answer for k=1 is 2.

Sample Input 2

4
1 2 3 4

Sample Output 2

0
0
0
0

No two balls have equal numbers written on them.

Sample Input 3

5
3 3 3 3 3

Sample Output 3

6
6
6
6
6

Any two balls have equal numbers written on them.

Sample Input 4

8
1 2 1 4 2 1 4 1

Sample Output 4

5
7
5
7
7
5
7
5



Sample input:
5
1 1 2 1 2


Sample output:
2
2
3
2
3

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))

S=[0 for j in range(N+1)]
count=0
for i in range(N):
  S[A[i]]+=1
for i in range(N+1):
  count+=S[i]*(S[i]-1)//2
for i in range(N):
  print(count-(S[A[i]]-1))

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = list(map(int, input().split()))

if len(a) == len(set(a)):
    for i in range(n):
        print(0)
else:
    kw = Counter(a)
    ans = sum([x * (x - 1) // 2 for x in kw.values()])

    for i in range(n):
        print(ans - kw[a[i]] + 1)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

counts = {}
for i in range(N):
    a = A[i]
    if a in counts:
        counts[a] += 1
    else:
        counts[a] = 1

# print(counts)

ans_memory = {}
ans_memory_val = {}
for k in range(N):
    if A[k] in ans_memory:
        print(ans_memory[A[k]])
        continue
    if counts[A[k]] in ans_memory_val:
        print(ans_memory_val[counts[A[k]]])
        continue

    counts_tmp = counts.copy()
    counts_tmp[A[k]] -= 1

    # print(counts_tmp)
    ans = 0
    for v in counts_tmp.values():
        ans += v * (v - 1) // 2
    ans_memory[A[k]] = ans
    ans_memory_val[counts[A[k]]] = ans
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

d = {}
for a in A:
  d[a] = d.get(a, 0) + 1
sum = sum([v*(v-1)/2 for v in d.values()]) 

for i in range(N):
  print(int(sum-d[A[i]]+1))

Submission status: Accepted

Solution code:
import collections
n=int(input())
a=list(map(int, input().split(' ')))
c = collections.Counter(a)

def n_c_2(val):
  ret = 0
  if val > 1:
    ret = (val)*(val-1)//2
  return ret

org_nc2 = {}
org_minus1_nc2 = {}
sumall = 0
for k in list(c.keys()):
  org_nc2[k] = n_c_2(c[k])
  org_minus1_nc2[k] = n_c_2(c[k] - 1)
  sumall += org_nc2[k]
for d in a:
  ans = sumall - org_nc2[d] + org_minus1_nc2[d]
  print (ans)

Submission status: Accepted

Solution code:
n = int(input())
a = input().split()

a = list(map(lambda x:int(x), a))

counter = [0] * 200005
choice = [0] * 200005
choice_minus1 = [0] * 200005
table = [-1] * 2000005
sum = 0

for i in range(0, len(a)):
    counter[a[i]] = counter[a[i]] + 1

for i in range(0, len(counter)):
    tmp_choice = int(counter[i] * (counter[i]-1) / 2)
    if tmp_choice <= 0:
        choice[i] = 0
    else:
        choice[i] = tmp_choice
        sum = sum + tmp_choice
    
    tmp_choice = int((counter[i]-1) * (counter[i]-2) / 2)
    if tmp_choice <= 0:
        choice_minus1[i] = 0
    else:
        choice_minus1[i] = tmp_choice

for i in range(0, len(a)):
    if table[a[i]] == -1:
        print(sum-choice[a[i]]+choice_minus1[a[i]])
        table[a[i]] = sum-choice[a[i]]+choice_minus1[a[i]]
    else:
        print(table[a[i]])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

MOD = 10**9
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

N = int(input())
A = list(map(int, input().split()))
dic = {}
for a in A:
    if a in dic: dic[a] += 1
    else: dic[a] = 1

C = {0:0}

sum_ni = 0
for i in range(1, N+1):
    C[i] = i*(i-1)//2

D = {}
for k, v in dic.items():
    sum_ni += C[v]


for k, v in dic.items():
    D[k] = sum_ni - C[dic[k]] + C[dic[k]-1]

for i in range(N):
    print(D[A[i]])

Submission status: Accepted

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
N=int(input())
count=[0]*N
A=list(map(int,input().split()))
for i in range(N):
    count[A[i]-1]+=1
#print(count)
k=max(count)
"""
kari=count.copy()
kari.sort()
tekitou=kari[1]"""
#print(k)
ans=0
for i in range(N):
    if count[i]>=2:
        ans+=cmb(count[i],2)
#print(ans)
pin=cmb(k,2)
pink=cmb(k-1,2)
#print(cmb(0,2))
for i in range(N):
    unti=count[A[i]-1]
    #print(unti,"unti")
    if unti==k:
        print(ans-pin+pink)
    else:
        if unti>2:
            print(ans-cmb(unti,2)+cmb(unti-1,2))
        elif unti==2:
            print(ans-1)
        else:
            print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = tuple(map(int, input().split()))
C = Counter(A)

MX = sum(v*(v-1) for v in C.values())//2
for i in range(N):
    print(MX-C[A[i]]+1)

Submission status: Accepted

Solution code:
def compute(x):
	if x>=2:
		return (x*(x-1)//2)
	else:
		return 0

n = int(input())
a = list(map(int,input().split()))
d = {}
for i in a:
	if i not in d:
		d[i] = 1
	else:
		d[i] += 1
s = 0
for j in d:
	s += compute(d[j])

for i in a:
	temp = s - compute(d[i])
	temp = temp + compute(d[i]-1)
	print(temp)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))


dict_A={}
B=list(set(A))
sum=0


for a in A:
    if a not in dict_A.keys():
        dict_A[a]=1
    else:
        dict_A[a]+=1
for b in B:
    sum+=dict_A[b]*(dict_A[b]-1)//2

for a in A:
    print(sum-dict_A[a]+1)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
c=[0]*n
ans=0

for i in range (n):
  c[l[i]-1]+=1
  
for j in range (n):
  ans+=int(c[j]*(c[j]-1)/2)

for k in range (n):
  h=c[l[k]-1]
  if h==0 or h==1:
    print (ans)
  else:
    print(ans-int(h*(h-1)/2)+int((h-1)*(h-2)/2))

Submission status: Accepted

Solution code:
import math

N = int(input())
A = list(map(int,input().split()))

num = [0] * N

for i in A:
    num[i - 1] = num[i - 1] + 1

a = [0] * N
b = [0] * N

for i in range(N):
    if num[i] >= 2:
        a[i] = (num[i] - 1) * (num[i] - 2) // 2
        b[i] = num[i] - 1

sum_a = sum(a)
sum_b = sum(b)

for i in A:
    print(sum_a + sum_b - b[i - 1])

Submission status: Accepted

Solution code:
import collections as col

def comb(n):
	ret = 0
	if n == 0:
		ret = 0
	else:
		ret = n * (n-1) / 2

	return ret

if __name__ == '__main__':
	N = int(input())
	v = [int(a) for a in input().split()]

	count = col.Counter(v)

	ans = 0

	for i in range(N):
		k = i + 1
		c = count[k]
		if c > 1:
			ans += comb(c)

	for i in range(N):
		c = count[v[i]]
		if c > 1:
			ANS = ans - (c - 1)
		else:
			ANS = ans
		print(int(ANS))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0] * 200001

for i in range(N):
    j = A[i]
    B[j] = B[j] + 1
ans = 0

for i in range(200001):
    y = B[i]
    ans = ans +(y * (y - 1) / 2 )
    
for i in range(N):
    j = A[i]
    p = ans - B[j] + 1
    p = int(p)
    print(p)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))

l_dic = {}
for i in l:
  if i in l_dic:
    l_dic[i] += 1
  else:
    l_dic[i] = 1
cnt_dic = {}
for i, j in l_dic.items():
  cnt_dic[i] = j*(j-1)//2
ans = 0
for i, j in cnt_dic.items():
  ans += j

for i in l:
  print(ans - cnt_dic[i] + (l_dic[i]-1)*(l_dic[i]-2)//2)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
L = list( map(int,input().split()) )

D = np.zeros(2*(10**5)+1,dtype=int)


for i in L:
    D[i] += 1

Dcopy = D

# D = np.where(D>1,(D-1)*D/2,0)
D = D*(D-1)/2
temp = int(D.sum())

for j in range(len(L)):
    if Dcopy[L[j]] > 1:
        print(temp - Dcopy[L[j]] + 1)
    else:
        print(temp)

Submission status: Accepted

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
# import numpy as np
def resolve():
    N = ir()
    # A = np.array(lr(), np.int32)
    A = lr()
    A = [[A[i], i] for i in range(N)]
    A.append([2*10**5+1, N+1])
    A = sorted(A, key=lambda x: x[0])
    c = []
    d = []
    e = []
    tmp = 1
    st = 0
    for i in range(N+1):
        if tmp == A[i][0]:
            st += 1
        else:
            if st > 1:
                c.append(tmp)
                d.append(st)
                e.append(st*(st-1)//2)
            else:
                c.append(tmp)
                d.append(st)
                e.append(0)
            tmp = A[i][0]
            st = 1
    ans = []
    tmp = 0
    # print(c, d, e)
    se = sum(e)
    for i in range(N):
        if A[i][0] > c[tmp]:
            tmp += 1
        num = d[tmp]
        plu = 0
        if num > 2:
            plu = (num-1)*(num-2)//2
        ans.append([se-e[tmp]+plu, A[i][1]])
    # print(ans)
    # print(iA)
    ans = sorted(ans, key=lambda x: x[1])
    for i in range(N):
        print(ans[i][0])

resolve()

Submission status: Accepted

Solution code:
import collections
N = int(input())
l = list(map(int,input().split()))
c = collections.Counter(l)
cnt = 0
for v in c.values():
    cnt += v*(v-1)//2
    
for i in range(N):
  print(cnt - c[l[i]] + 1)

Submission status: Accepted

Solution code:
N=int(input())
A= list(map(int, input().split()))

d=[0]*(N+1)

for i in range (0,N):
    c=A[i]
    d[c]+=1
    
z=0

for x in range (1,N+1):
    z+=d[x]*(d[x]-1)//2
    
for y in range (0,N):
    r=A[y]
    print(z+1-d[r])

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]

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

s = 0
for i in range(N):
  s += B[i]*(B[i]-1)//2

for i in range(N):
  print(s-B[A[i]-1]+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n = int(input())
a = list(map(int, input().split()))

import collections

c = collections.Counter(a)

combinations = [0] + [0] * n
for i in range(0, n+1):
    combinations[i] = (i * (i-1)) // 2
memo = [0] + [0] * n

for k in c:
    memo[k] = combinations[c[k]]

total = sum(memo)
for i in a:
    print(total - memo[i] + combinations[c[i] - 1])

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

def ncr(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


n = int(input())
a = list(map(int, input().split()))

numList = [0] * (n+1)
numSet = set()

ncrList = [0] * (n+1)

resultList = [0] * (n+1)
resultSet = set()

for i in range(len(a)):
    numList[a[i]] += 1
    if(numList[a[i]]==2):
        numSet.add(a[i])

sums = 0
for i in numSet:
    ncrList[i] = ncr(numList[i], 2)
    sums += ncrList[i]

for i in range(len(a)):
    if(a[i] in resultSet):
        print(resultList[a[i]])
        continue
    s = sums
    if(a[i] in numSet):
        if(numList[a[i]] == 2):
            s -= 1
        else:
            s -= ncrList[a[i]]
            s += ncr(numList[a[i]]-1, 2)
    print(s)
    resultList[a[i]] = s
    resultSet.add(a[i])

Submission status: Accepted

Solution code:
n = int(input())
li = list(map(int,input().split()))
ma = {}
for l in li:
    if l in ma:
        ma[l] += 1
    else:
        ma[l] = 1
all_sum = 0
for m in ma.values():
    if all_sum == 0 and m >= 2:
        all_sum = m*(m-1)//2
    elif m >= 2:
        all_sum = all_sum + m*(m-1)//2
for l in li:
    if ma[l] >=2:
        tmp_sum = all_sum - (ma[l]*(ma[l]-1)//2)
        if ma[l] >=3:
            tmp_sum += ((ma[l]-1)*(ma[l]-2)//2)
        print(tmp_sum)
    else:
        print(all_sum)

Submission status: Accepted

Solution code:

def select2( val ):
  return( val*(val-1) // 2 ) 

N = int(input())
elms = input().split(" ")


ielms = []
for elm in elms:
  ielms.append( int(elm ))



test_dict = {}

for ielm in ielms:
  if( ielm in test_dict.keys() ):
    test_dict[ielm] += 1
  else:
    test_dict[ielm] = 1

total = 0
for dkey in test_dict.keys():      
  total += select2( test_dict[dkey] )
      
for ielm in ielms:
  print(total - select2( test_dict[ielm] ) + select2( test_dict[ielm]-1 ))

Submission status: Accepted

Solution code:
def nc2(n):
	if n<2:
		return 0
	else:
		return (n * (n-1))//2
n = int(input())
li = list(map(int, input().split()))
s=0; 
d2={}
import collections as cl
d = cl.Counter(li)
for k, v in d.items():
	d2[k] = [nc2(v), nc2(v-1)]
	for v in d2[k]:
		s+=v
		break
# print(d2,s)
for i in li:
	print(s-(d2[i][0])+d2[i][1])
# print(d)
# for i in li:
# 	ans = 0
# 	for k,v in d.items():
# 		if k!=i:
# 			ans+=nc2(v)
# 		else:
# 			ans+=nc2(v-1)
# 	print(ans)

Submission status: Accepted

Solution code:
import collections
temp = 0
n = input()
li = list(map(int,input().split()))
c = collections.Counter(li)
c_items = list(c.items())
for j in c_items:
    temp += ((j[1] * (j[1]-1)) // 2)
for i in li:
    print(temp - (c[i]-1))

Submission status: Accepted

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10**6)

def fn(n):
    if n <= 1:
        return 0
    return n - 1 + fn(n-1)

N = int(input())
A = list(map(int, input().split()))

c = Counter(A)
kumi = 0
for k, v in c.items():
    kumi += fn(v)

for ai in A:
    print(kumi - (c[ai] - 1))

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
def cmb(n,r):
    r=min(n-r,r)
    if r==0:
        return 1
    over=reduce(mul,range(n,n-r,-1))
    under=reduce(mul,range(1,r+1))
    return over//under

N=int(input())
A=list(map(int,input().split()))

data=[0]*(N+1)
for a in A:
    data[a]+=1

num=0
for i in range(N+1):
    if data[i]>=2:
        num+=cmb(data[i],2)
        
for k in range(N):
    if data[A[k]]>=2:
        print(num-data[A[k]]+1)
    else:
        print(num)

Submission status: Accepted

Solution code:
A = input()
B = list(input().split())
import collections
C = collections.Counter(B)
list_after = {}
list_n = C.items()
total = 0
for i in list_n:
    total += i[1] * (i[1]-1) / 2
for i in list_n:
    list_after[i[0]] = total - (i[1] * (i[1]-1) / 2 - (i[1]-1) * (i[1]-2) / 2)
for i in B:
    print(int(list_after[i]))

Submission status: Accepted

Solution code:
import math
 


def nC2(i):
    if i<=1:
        return 0
    return i*(i-1)//2

def compute(count):
    total = 0
    for i in count:
        total += nC2(i)
    return total


N = int(input())
data = list(map(int,input().split()))

count = [0] * (N+1)

for value in data:
    count[value] += 1
    
    
total = compute(count)    

for value in data:
    remove = nC2(count[value])
    add = nC2(count[value]-1)

    print(total-remove+add)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int,input().split()))
ans = 0
ansl = 0
d = {}
if len(l) == len(set(l)):
  for i in range(len(l)):
    print(0)
else:
  for s in l:
    if s not in d:
      d[s] = 1
    else:
      d[s] += 1
  for j,k in d.items():
    ans += k*(k-1)//2
  ansl = ans
  for i in range(n):
    ans = ansl
    x = d[l[i]]
    ans -= x - 1
    print(ans)

Submission status: Accepted

Solution code:
import math
n=int(input())
l=list(map(int,input().split()))
d={}
for i in l:
    if i in d:
        d[i]+=1 
    else:
        d[i]=1 
count=0
for k in d.keys():
        x=d[k]
        if x<2:
            count+=0
        else:
            count+=x*(x-1)//2

for i in l:
    x=d[i]
    #print(i, x)
    if x>=2:
        val=x*(x-1)//2
        ans=count-val
        if x>=3:
            x-=1
            val1=x*(x-1)//2
        else:
            val1=0
        ans+=val1
    else:
        if x==2:
            ans=count-1 
        else:
            ans=count 
    print(int(ans))

Submission status: Accepted

Solution code:
import collections
import math
 
def comb(n, r):
    if n < 2:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
 
 
N = int(input())
L = input().split(" ")
 
c = collections.Counter(L)
 
d = {}
tmp_total = 0 
 
memo1 = {}
L2 = {}
 
for i in c:
    if c[i] not in memo1.keys():
        tmp = comb(c[i], 2)
        memo1[c[i]] = tmp
        tmp_total += tmp
    else:
        tmp_total += memo1[c[i]]
        
total = tmp_total
 
for i in L:
    ans = total - memo1[c[i]] + memo1[c[i]]*(c[i]-2)//c[i]
    print(ans)

Submission status: Accepted

Solution code:
import collections

n = int(input())
a = list(map(int, input().split()))

C = collections.Counter(a)

ans = [0] * (10 ** 6)
cnt = 0
# print(C)
for i, j in C.items():
    cnt += j * (j - 1) // 2

# print(ans)
# print(cnt)
for i in range(len(a)):
    if C[a[i]] > 0:
        print(cnt - (C[a[i]]-1))
    else:
        print(cnt)

Submission status: Accepted

Solution code:
import collections
n = int(input())
a = list(map(str,input().split()))
c = collections.Counter(a)
all_answer = 0
for _,b in c.items():
	all_answer += b*(b-1)//2
for i in a:
	b = c[i]
	print(all_answer-b*(b-1)//2+(b-1)*(b-2)//2)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
import copy
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n = int(input())
A = list(map(int,input().split()))
aset = set(A)
aDict = {}
for aName in aset:
    aDict.update({aName:0})
for a in A:
    aDict[a] += 1

combNumDict = {}
sum = 0
for i in aset:
    if aDict[i] == 0 or aDict[i] == 1:
        tmpsum = 0
    else:
        tmpsum = cmb(aDict[i],2)
    combNumDict.update({i:tmpsum})
    sum += tmpsum
for i in range(n):
    k = A[i]
    if aDict[k] == 1:
        print(sum)
    else:
        if aDict[k] == 2:
            tmp = 1
        else:
            tmp = cmb(aDict[k],2)-cmb(aDict[k]-1,2)
        print(sum-tmp)

Submission status: Accepted

Solution code:
n = int(input())
list = list(map(int,input().split()))
di = {}
for i in range(n):
	k = list[i]
	if k not in di:
		di[k]=1
	else:
		di[k]+=1
"""
list_del=[]
for key in di.keys():
	if di[key]==1:
		list_del.append(key)
for i in range(len(list_del)):
	di.pop(list_del[i])
"""
	
su=0
for valu in di.values():
	su += valu*(valu-1)/2
	
for i in range(n):
	k = list[i]
	l = di[k]
	su_ch = su
	su_ch -= l*(l-1)/2
	su_ch += (l-1)*(l-2)/2
	print(int(su_ch))

Submission status: Accepted

Solution code:
from collections import defaultdict
import math
n = int(input())
a = [int(x) for x in input().split()]
ans = []
tmp_sum = 0
m_dic,c_dic = defaultdict(int),defaultdict(int)
for x in a:
    m_dic[x] += 1

for value in m_dic.values():
    if value > 1:
        tmp_sum += math.factorial(value) // (math.factorial(value - 2) * math.factorial(2))

for x in a:
    print(tmp_sum-m_dic[x]+1)

Submission status: Accepted

Solution code:
n=int(input())
al=list(map(int,input().split()))

from collections import Counter
myc=Counter(al)
val=list(myc.values())
key=list(myc.keys())
val2=list(map(lambda x:x-1,val))

nc2=[0]*n
nc22=[0]*n

for i in range(len(key)):
    p=val[i]
    q=val2[i]
    if q>=2:
        nc2[key[i]-1]=p*(p-1)//2
        nc22[key[i]-1]=q*(q-1)//2
    elif q==1:
        nc2[key[i]-1]=1
        nc22[key[i]-1]=0
    else:
        pass

sum1=sum(nc2)

for i in range(n):
    j=al[i]-1
    print(sum1-nc2[j]+nc22[j])

Submission status: Accepted

Solution code:
# Problem D -Banned K

# input
n = int(input())
a_list = list(map(int, input().split()))

# initialization
cur_dic = {}
cur_sum = 0
for a in a_list:
    if a in cur_dic:
        cur_dic[a] += 1
    else:
        cur_dic[a] = 1

for c in cur_dic:
    num = cur_dic[c]
    cur_sum += num * (num-1) / 2

for i in range(len(a_list)):
    a = a_list[i]
    d = cur_dic[a]
    # 減らす
    if d > 1:
        cur_sum -= d * (d-1) / 2
    cur_dic[a] -= 1

    # output
    tmp = cur_sum
    if cur_dic[a] > 1:
        tmp = cur_sum + cur_dic[a] * (cur_dic[a] - 1) / 2 # update
    print("%d"%(tmp))

    # 増やす
    if d > 1:
        cur_sum += d * (d-1) / 2
    cur_dic[a] += 1

Submission status: Accepted

Solution code:
import sys
import collections

n = int(input())
a = list(map(int, sys.stdin.readline().split()))
c = collections.Counter(a)
ans = [0 for i in range(sorted(c.keys())[-1]+1)]

for i in c.keys():
    ans[i] = c[i]*(c[i]-1)//2

sans = sum(ans)
for i in a:
    print(sans - ans[i] + ans[i]*(c[i]-2)//c[i])

Submission status: Accepted

Solution code:
N_max = 2*(10**5)
N = int(input())

A = list(map(int, input().split()))

array = sorted(A)
quantity_of_num = [0]*(N_max + 1) # kという値がquantity_of_num[k]個あることを示す
type_index = list() # 文字の種類を昇順で記録していく配列。　len(type_index)が文字の種類数

count = 1 # 各文字が何個あるかの記録作業
for i in range(N-1):
    if array[i] == array[i+1]:
        count += 1
    else:
        type_index.append(array[i])
        quantity_of_num[array[i]] = count

        count = 1
type_index.append(array[i+1])
quantity_of_num[array[i+1]] = count

# type_index と　quantity_of_num の印字用
# for i in range(len(type_index)):
#     print(type_index[i], end="")
# print()
# for i in range(len(type_index)):
#     print(quantity_of_num[type_index[i]], end="")
# print()

total = 0 #k番目を除外せずに同じ数字の取り方が何通りあるかを検証
for i in range(len(type_index)):
        quantity = quantity_of_num[type_index[i]]
        # total の計算の挙動確認用
        # print("i = ", i, "quantitiy = ", quantity, "sum = ", quantity*(quantity - 1) // 2)
        total += quantity*(quantity - 1) // 2

for k in range(N):

    # k番目の数字から選んでいた部分を修正すれば良い
    # A[k] がk番目の数字
    quantity = quantity_of_num[A[k]]
    ans = total - ( quantity*(quantity-1) // 2) + ( (quantity-1)*(quantity-2) // 2)
    
    print(ans)

Submission status: Accepted

Solution code:
import math

N = int(input())
A = list(map(int,input().split()))

def comb(n):
  r = 2
  if n <= 1:
    return 0
  if n - r < r: r = n - r
  if r == 0: return 1
  if r == 1: return n
  
  numerator = [n - r + k + 1 for k in range(r)]
  denominator = [k + 1 for k in range(r)]
  
  for p in range(2,r+1):
    pivot = denominator[p - 1]
    if pivot > 1:
      offset = (n - r) % p
      for k in range(p-1,r,p):
        numerator[k - offset] /= pivot
        denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
dic = {}
#まず最初に、グルーピング(グルーピングの時点で辞書化が必要)
for a in A:
  if a in dic:
    dic[a][0] += 1
  else:
    dic[a] = [1]

#辞書にコンビネーションをvalueとして書き込んでいく
for v in dic.values():
  v.append(comb(v[0]))
  v.append(comb(v[0]-1))

#各グループのlen(g)C2を総計して変数grandとして保持しておく
grand = 0
for v in dic.values():
  grand += v[1]
  
for a in A:
  output = grand - dic[a][1] + dic[a][2]
  print(output)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
L = Counter(A)
anss = {}
sum_ans = sum([i*(i-1)//2 for i in L.values() if i >= 2])
for k,v in L.items():
    anss[k] = sum_ans - (v*(v-1)//2) + ((v-1)*(v-2)//2)
for i in A:
    print(anss[i])

Submission status: Accepted

Solution code:
# ABC159_D
from collections import defaultdict as dd
n=int(input())
a=list(map(int,input().split()))
d=dd(int)
for aa in a:
    d[aa]+=1
a_sum=0
for k,v in d.items():
    # if v>=2:
    a_sum+=v*(v-1)//2

for i,aa in enumerate(a):
    s=a_sum
    t=d[a[i]]
    s-=t*(t-1)//2
    t-=1
    s+=t*(t-1)//2
    print(s)
# for k,v in d.items()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()

	ap = {}
	for i in A:
		if i in ap:
			ap[i] += 1
		else:
			ap[i] = 1

	mmax = 0
	for k, v in ap.items():
		if v > 1:
			mmax += cmb(v, 2)

	#print(mmax)
	for i in A:
		if mmax == 0:
			print(0)
			continue
		conts = ap[i]
		conts2 = conts -1
		#print("{} {}".format(conts, conts2))
		m = 0
		p = 0
		if conts == 2:
			m = cmb(conts, 2)
		elif conts == 1:
			print(mmax)
			continue
		else:
			m = cmb(conts, 2)
			p = cmb(conts2, 2)
		#print("{} {}".format(m, p))
		aaa = mmax - m + p
		print(aaa)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def int_sqrt2(n):
    def f(prev):
        while True:
            m = (prev + n / prev) / 2
            if m >= prev:
                return prev
            prev = m

    return f(int(math.sqrt(n) * (1 + 1e-10)))

# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
nl = {}
cal = {}
kal = {}
cl = {}
all = 0
for num in l:
  if num in nl:
    nl[num] = nl[num] + 1
  else:
    nl[num] = 1
for n in nl:
  if nl[n] > 1:
    cal[n] = nl[n] * (nl[n]-1) / 2
  else:
    cal[n] = 0
  if nl[n]-1 > 1:
    kal[n] = (nl[n]-1) * (nl[n]-2) / 2
  else:
    kal[n] = 0
  all += cal[n]
for n in nl:
  cl[n] = int(all - cal[n] + kal[n])
for i in l:
  print(cl[i])

Submission status: Accepted

Solution code:
N = int(raw_input())
A = map(int, raw_input().split())

#N = 200000
#A = [200000]*N

count = [0]*(N+2)
for i in range(N):
    id = A[i]
    count[id] = count[id]+1

sumN = long(0)
for i in range(N+1):
    sumN = sumN + long(long(count[i]*(count[i]-1))/2)

#print answer
for i in range(N):
    id = A[i]
    sumz = sumN - (count[id] - 1)
    print(sumz)

Submission status: Accepted

Solution code:
N = int(input())
Ai = list(map(int,input().split()))
Aisort = sorted(Ai) + [-1]
Aidic = {}
cnt = 1
for i in range(1,N+1):
    if Aisort[i] != Aisort[i-1]:
        Aidic.update([(str(Aisort[i-1]), cnt)])
        cnt = 1
    else:
        cnt = cnt + 1

cnt = 0
for i, indx in enumerate(Aidic):
    num = int(Aidic[indx])
    cnt = cnt + num*(num-1)//2


for A in Ai:
    num = int(Aidic[str(A)])
    num = cnt - (num-1)
    print(num)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

n = int(input())
A = [int(i) for i in input().split()]
d = {}

As = set(A)

for a in A:
    if a in d:
        d.update({a: d.get(a) + 1})
    else:
        d.update({a: 1})

summ = 0
for x in As:
    y = d.get(x)
    summ += y*(y-1) // 2

for a0 in A:
    print(summ - (d.get(a0)-1))

Submission status: Accepted

Solution code:
import collections

N = int(input())
A = list(map(int,input().split()))
a = collections.Counter(A)
v = a.values()
l_v = list(v)

#合計
s = 0
for i in range(len(l_v)):
    n = l_v[i]-1
    s += n*(n+1)//2
#カウント
for i in range(N):
    print(s-(a[A[i]]-1))

Submission status: Accepted

Solution code:
from collections import Counter
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N = int(input())
a = list(map(int, input().split()))

a_cnt = Counter(a)

a_comb = {}
for key, val in a_cnt.items():
    if val >= 2:
        a_comb[key] = combinations_count(val, 2)
    else:
        a_comb[key] = 0

sum_v = sum(a_comb.values())

for num in a:
    print(sum_v-a_cnt[num]+1)