ABC347Eを解いた【累積和】

筆者はレート800前後の茶～緑コーダ

ABC347のE問題を解いていく

実装コード

各クエリでの集合の要素数を記憶して累積和

各数列の要素が集合に入っていた区間を記憶して累積和から区間和を求める

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from itertools import product, accumulate, groupby
import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

d = defaultdict(deque)
def main():
    N, Q = rLI()
    X = rLI1()
    s = set()
    v = 0
    Y = [0]
    V = [0]
    A = [0] * N
    for i, x in enumerate(X):
        d[x].append(i)
        if x in s:
            s.remove(x)
            v-=1
        else:                           
            s.add(x)
            v+=1
        Y.append(Y[-1]+v)
        V.append(v)
    # err(V)
    # err(Y)
    for k,q in d.items():
        # err(k,q)
        a = 0
        while q:
            if len(q) >= 2:
                j = q.popleft()
                v = Y[q.popleft()] - Y[j] 
            else:
                v = Y[-1] - Y[q.popleft()]
            # err(k,a,v)
            a+=v
        A[k] = a
    print(*A)
    
if __name__ == '__main__':
    main()

まとめ

手順が複雑で難しそうだったが
クエリごとではなく数列の各要素に着目すればシンプルに解けた

物事の視点を変える重要性を感じる問題だった。