↓Skip to main content
  1. Posts/

CodeForces-1789C Serval and Toxel's Arrays

·1 min·
Table of Contents

CodeForces-1789C Serval and Toxel’s Arrays #

Solution 1 #

正难则反, 此时考虑每个元素的贡献只需要统计其出现次数.

代码如下:

from collections import defaultdict

if __name__ == '__main__':
    t = int(input())
    while t > 0:
        t -= 1
        tmp = [int(x) for x in input().split()]
        n, m = tmp[0], tmp[1]
        a = [int(x) for x in input().split()]
        book = [0] * (n + m + 1)
        for x in a:
            book[x] += m + 1
            
        ans = n * m * (m + 1)
        for i in range(m):
            tmp = [int(x) for x in input().split()]
            p, v = tmp[0], tmp[1]
            if v != a[p - 1]: 
                book[a[p - 1]] -= m - i
                a[p - 1] = v
                book[a[p - 1]] += m - i
        for x in book:
            ans -= x * (x - 1) // 2
        print(ans)