Stone Age Problem (Codeforces 1679B)
Tags: Implement, data structures

Once upon a time Mike and Mike decided to come up with an outstanding problem for some stage of ROI (rare olympiad in informatics). One of them came up with a problem prototype but another stole the idea and proposed that problem for another stage of the same olympiad. Since then the first Mike has been waiting for an opportunity to propose the original idea for some other contest... Mike waited until this moment!You are given an array $$$a$$$ of $$$n$$$ integers. You are also given $$$q$$$ queries of two types:  Replace $$$i$$$-th element in the array with integer $$$x$$$.  Replace each element in the array with integer $$$x$$$. After performing each query you have to calculate the sum of all elements in the array.

Input: The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the number of elements in the array and the number of queries, respectively.The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — elements of the array $$$a$$$.Each of the following $$$q$$$ lines contains a description of the corresponding query. Description begins with integer $$$t$$$ ($$$t \in \{1, 2\}$$$) which denotes a type of the query:  If $$$t = 1$$$, then two integers $$$i$$$ and $$$x$$$ are following ($$$1 \le i \le n$$$, $$$1 \le x \le 10^9$$$) — position of replaced element and it's new value.  If $$$t = 2$$$, then integer $$$x$$$ is following ($$$1 \le x \le 10^9$$$) — new value of each element in the array. 

Output: Print $$$q$$$ integers, each on a separate line. In the $$$i$$$-th line print the sum of all elements in the array after performing the first $$$i$$$ queries.

Note: Consider array from the example and the result of performing each query:  Initial array is $$$[1, 2, 3, 4, 5]$$$.  After performing the first query, array equals to $$$[5, 2, 3, 4, 5]$$$. The sum of all elements is $$$19$$$.  After performing the second query, array equals to $$$[10, 10, 10, 10, 10]$$$. The sum of all elements is $$$50$$$.  After performing the third query, array equals to $$$[10, 10, 10, 10, 11$$$]. The sum of all elements is $$$51$$$.  After performing the fourth query, array equals to $$$[10, 10, 10, 1, 11]$$$. The sum of all elements is $$$42$$$.  After performing the fifth query, array equals to $$$[1, 1, 1, 1, 1]$$$. The sum of all elements is $$$5$$$. 

Sample Inputs:
5 5
1 2 3 4 5
1 1 5
2 10
1 5 11
1 4 1
2 1

Sample Outputs:
19
50
51
42
5

Solution (Python):
import sys
import copy
import heapq
import bisect
import functools
from math import *
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import groupby
import itertools
from itertools import accumulate
from decimal import Decimal, ROUND_HALF_UP
readline = lambda : sys.stdin.readline().rstrip()

def solve():
    (n, m) = map(int, readline().split())
    a = list(map(int, readline().split()))
    (ans, same) = (0, 0)
    mp = defaultdict(int)
    for (i, x) in enumerate(a, 1):
        mp[i] = x
        ans += x
    while m > 0:
        line = list(map(int, readline().split()))
        if line[0] == 1:
            (_, x, v) = line
            if x in mp:
                ans += v - mp[x]
            else:
                ans += v - same
            mp[x] = v
        else:
            ans = n * line[1]
            same = line[1]
            mp.clear()
        print(ans)
        m -= 1

def main():
    t = 1
    for i in range(t):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
import sys
import copy
import heapq
import bisect
import functools
from math import *
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import groupby
import itertools
from itertools import accumulate
from decimal import Decimal, ROUND_HALF_UP
readline = lambda : sys.stdin.readline().rstrip()

def solve():
    (n, m) = map(int, readline().split())
    a = list(map(int, readline().split()))
    (ans, same) = (0, 0)
    mp = defaultdict(int)
    for (i, x) in enumerate(a, 1):
        mp[i] = x
        ans += x
    while m > 0:
        line = list(map(int, readline().split()))
        if line[0] == 1:
            (_, x, v) = line
            if x in mp:
                ans += v - mp[x]
            else:
                ans += v - same
            mp[x] = v
        else:
            ans = n * line[1]
            same = line[1]
            mp.clear()
        print(ans)
        m -= 1

def main():
    t = 1
    for i in range(t):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
f = open(0)
R = lambda : map(int, next(f).split())
(n, q) = R()
d = {}
i = v = r = 0
for x in R():
    r += x
    i += 1
    d[i] = x
while q:
    q -= 1
    (t, *x) = R()
    if t & 1:
        (i, x) = x
        r += x - d.get(i, v)
        d[i] = x
    else:
        d = {}
        (v,) = x
        r = v * n
    print(r)