-
Notifications
You must be signed in to change notification settings - Fork 15
/
candies.py
61 lines (53 loc) · 1.79 KB
/
candies.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
# Copyright (c) 2020 kamyu. All rights reserved.
#
# Google Kick Start 2020 Round C - Problem D. Candies
# https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff43/0000000000337b4d
#
# Time: O(N + QlogN)
# Space: O(N)
#
class BIT(object): # 0-indexed.
def __init__(self, nums, M): # Time: O(N)
self.__bit = [0]*(len(nums)+1) # Extra one for dummy node.
for i in xrange(1, len(self.__bit)):
sign = 1 if i%2 == 1 else -1
self.__bit[i] = sign*nums[i-1]*(i if M else 1) + self.__bit[i-1]
for i in reversed(xrange(1, len(self.__bit))):
self.__bit[i] -= self.__bit[i-(i&-i)]
def add(self, i, val): # Time: O(logN)
i += 1 # Extra one for dummy node.
while i < len(self.__bit):
self.__bit[i] += val
i += (i & -i)
def query(self, i): # Time: O(logN)
i += 1 # Extra one for dummy node.
ret = 0
while i > 0:
ret += self.__bit[i]
i -= (i & -i)
return ret
def update(A, T, MT, i, v):
diff = v-A[i]
sign = 1 if i%2 == 0 else -1
T.add(i, sign*diff)
MT.add(i, sign*diff*(i+1))
A[i] = v
def range_sum(bit, l, r):
return bit.query(r)-bit.query(l-1)
def candies():
N, Q = map(int, raw_input().strip().split())
A = map(int, raw_input().strip().split())
T, MT = BIT(A, False), BIT(A, True)
result = 0
for _ in xrange(Q):
o, a, b = raw_input().strip().split()
if o == 'U':
x, v = int(a)-1, int(b)
update(A, T, MT, x, v)
continue
l, r = int(a)-1, int(b)-1
sign = 1 if l%2 == 0 else -1
result += sign*(range_sum(MT, l, r) - l*range_sum(T, l, r))
return result
for case in xrange(input()):
print 'Case #%d: %s' % (case+1, candies())