Nastya and King-Shamans (Codeforces 992E)
Tags: Others, binary search

Nastya likes reading and even spends whole days in a library sometimes. Today she found a chronicle of Byteland in the library, and it stated that there lived shamans long time ago. It is known that at every moment there was exactly one shaman in Byteland, and there were n shamans in total enumerated with integers from 1 to n in the order they lived. Also, each shaman had a magic power which can now be expressed as an integer.The chronicle includes a list of powers of the n shamans. Also, some shamans can be king-shamans, if they gathered all the power of their predecessors, i.e. their power is exactly the sum of powers of all previous shamans. Nastya is interested in whether there was at least one king-shaman in Byteland.Unfortunately many of the powers are unreadable in the list, so Nastya is doing the following:  Initially she supposes some power for each shaman.  After that she changes the power of some shaman q times (the shamans can differ) and after that wants to check if there is at least one king-shaman in the list. If yes, she wants to know the index of any king-shaman. Unfortunately the list is too large and Nastya wants you to help her.

Input: The first line contains two integers n and q (1 ≤ n, q ≤ 2·105).The second line contains n integers a1, ..., an (0 ≤ ai ≤ 109), where ai is the magic power of the i-th shaman.After that q lines follow, the i-th of them contains two integers pi and xi (1 ≤ pi ≤ n, 0 ≤ xi ≤ 109) that mean that the new power of the pi-th shaman is xi.

Output: Print q lines, the i-th of them should contain  - 1, if after the i-th change there are no shaman-kings, and otherwise a single integer j, where j is an index of some king-shaman after the i-th change.If there are multiple king-shamans after each change, print the index of any of them.

Note: In the first example powers of shamans after the first change are equal to (2, 3). The answer equals  - 1, because the sum of powers of shamans before the first shaman is equal to 0, and before the second is equal to 2.In the second example after the first change the powers are equal to (1, 2, 3). The answer is equal to 3, because the power of the third shaman is equal to 3, and the sum of powers of the first and the second shaman is also 1 + 2 = 3. After the second change the powers become equal to (2, 2, 3), where the answer equals 2. After the third change the powers become equal to (2, 4, 3), where the answer equals  - 1. After the fourth change the powers become equal to (2, 4, 6), where the answer equals 3.

Sample Inputs:
2 1
1 3
1 2

3 4
2 2 3
1 1
1 2
2 4
3 6

10 7
0 3 1 4 6 2 7 8 10 1
2 5
1 3
9 36
4 10
4 9
1 2
1 0

Sample Outputs:
-1

3
2
-1
3

1
-1
9
-1
4
-1
1

Solution (Python):
import heapq
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_sum0(i):
    s = 0.0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s

def get_sum(s, t):
    ans = 0 if s > t else get_sum0(t) - get_sum0(s - 1)
    return ans

def add(i, x):
    while i < len(tree):
        tree[i] += x
        i += i & -i
(n, q) = map(int, input().split())
a = [0] + list(map(int, input().split()))
h = [[] for _ in range(31)]
for i in range(1, n + 1):
    heapq.heappush(h[a[i].bit_length()], i)
tree = [0] * (n + 1)
for i in range(1, n + 1):
    tree[i] += a[i] + 0.0
    j = i + (i & -i)
    if j < len(tree):
        tree[j] += tree[i]
u = [-1] * (n + 1)
c = [0] * (n + 1)
for i in range(31):
    hi = h[i]
    if not len(hi):
        continue
    j = heapq.heappop(hi)
    (u[j], c[j]) = (0, get_sum0(j - 1))
    if not len(hi):
        heapq.heappush(hi, j)
        continue
    k = hi[0]
    (u[k], c[k]) = (0, get_sum0(k - 1))
    heapq.heappush(hi, j)
ans = []
inf = pow(10, 9) + 1
for z in range(q):
    (p, x) = map(int, input().split())
    d = x - a[p]
    a[p] = x
    if len(ans) and (not d):
        ans0 = ans[-1]
        ans.append(ans0)
        continue
    add(p, d)
    heapq.heappush(h[x.bit_length()], p)
    ans0 = inf
    for i in range(31):
        hi = h[i]
        while hi and a[hi[0]].bit_length() ^ i:
            heapq.heappop(hi)
        if not len(hi):
            continue
        j = heapq.heappop(hi)
        if u[j] == z:
            s = c[j] if j <= p else c[j] + d
        else:
            s = get_sum0(j - 1)
        (u[j], c[j]) = (z, s)
        if s == a[j]:
            ans0 = min(ans0, j)
        while hi and (a[hi[0]].bit_length() ^ i or j == hi[0]):
            heapq.heappop(hi)
        if not len(hi):
            heapq.heappush(hi, j)
            continue
        k = hi[0]
        if u[k] == z:
            s = c[k] if k <= p else c[k] + d
        else:
            s = get_sum0(k - 1)
        (u[k], c[k]) = (z, s)
        if s == a[k]:
            ans0 = min(ans0, k)
        heapq.heappush(hi, j)
    ans0 = (ans0 + 1) % (inf + 1) - 1
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
(standard_input, packages, output_together) = (1, 1, 1)
(dfs, hashing, read_from_file) = (0, 0, 0)
de = 1
if 1:
    if standard_input:
        import io, os, sys
        input = lambda : sys.stdin.readline().strip()
        inf = float('inf')

        def I():
            return input()

        def II():
            return int(input())

        def MII():
            return map(int, input().split())

        def LI():
            return list(input().split())

        def LII():
            return list(map(int, input().split()))

        def LFI():
            return list(map(float, input().split()))

        def GMI():
            return map(lambda x: int(x) - 1, input().split())

        def LGMI():
            return list(map(lambda x: int(x) - 1, input().split()))
    if packages:
        from io import BytesIO, IOBase
        import math
        import random
        import os
        import bisect
        import typing
        from collections import Counter, defaultdict, deque
        from copy import deepcopy
        from functools import cmp_to_key, lru_cache, reduce
        from heapq import merge, heapify, heappop, heappush, heappushpop, nlargest, nsmallest
        from itertools import accumulate, combinations, permutations, count, product
        from operator import add, iand, ior, itemgetter, mul, xor
        from string import ascii_lowercase, ascii_uppercase, ascii_letters
        from typing import *
        BUFSIZE = 4096
    if output_together:

        class FastIO(IOBase):
            newlines = 0

            def __init__(self, file):
                self._fd = file.fileno()
                self.buffer = BytesIO()
                self.writable = 'x' in file.mode or 'r' not in file.mode
                self.write = self.buffer.write if self.writable else None

            def read(self):
                while True:
                    b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                    if not b:
                        break
                    ptr = self.buffer.tell()
                    (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
                self.newlines = 0
                return self.buffer.read()

            def readline(self):
                while self.newlines == 0:
                    b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                    self.newlines = b.count(b'\n') + (not b)
                    ptr = self.buffer.tell()
                    (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
                self.newlines -= 1
                return self.buffer.readline()

            def flush(self):
                if self.writable:
                    os.write(self._fd, self.buffer.getvalue())
                    (self.buffer.truncate(0), self.buffer.seek(0))

        class IOWrapper(IOBase):

            def __init__(self, file):
                self.buffer = FastIO(file)
                self.flush = self.buffer.flush
                self.writable = self.buffer.writable
                self.write = lambda s: self.buffer.write(s.encode('ascii'))
                self.read = lambda : self.buffer.read().decode('ascii')
                self.readline = lambda : self.buffer.readline().decode('ascii')
        sys.stdout = IOWrapper(sys.stdout)
    if dfs:
        from types import GeneratorType

        def bootstrap(f, stack=[]):

            def wrappedfunc(*args, **kwargs):
                if stack:
                    return f(*args, **kwargs)
                else:
                    to = f(*args, **kwargs)
                    while True:
                        if type(to) is GeneratorType:
                            stack.append(to)
                            to = next(to)
                        else:
                            stack.pop()
                            if not stack:
                                break
                            to = stack[-1].send(to)
                    return to
            return wrappedfunc
    if hashing:
        RANDOM = random.getrandbits(20)

        class Wrapper(int):

            def __init__(self, x):
                int.__init__(x)

            def __hash__(self):
                return super(Wrapper, self).__hash__() ^ RANDOM
    if read_from_file:
        file = open('input.txt', 'r').readline().strip()[1:-1]
        fin = open(file, 'r')
        input = lambda : fin.readline().strip()
        output_file = open('output.txt', 'w')

        def fprint(*args, **kwargs):
            print(*args, **kwargs, file=output_file)
    if de:

        def debug(*args, **kwargs):
            print('\x1b[92m', end='')
            print(*args, **kwargs)
            print('\x1b[0m', end='')

class FenwickTree:

    def __init__(self, nums):
        n = len(nums)
        self.n = n
        self.bit = nums[:]
        length = (self.n + 1).bit_length() - 1
        self.powers = [1 << i for i in range(length, -1, -1)]
        self.tot = sum(nums)
        for i in range(n):
            if i | i + 1 < n:
                self.bit[i | i + 1] += self.bit[i]

    def sum(self, r):
        res = 0
        while r >= 0:
            res += self.bit[r]
            r = (r & r + 1) - 1
        return res

    def rsum(self, l, r):
        return self.sum(r) - self.sum(l - 1)

    def add(self, idx, delta):
        if delta:
            while idx < self.n:
                self.bit[idx] += delta
                idx = idx | idx + 1
            self.tot += delta

    def bisect_max_smaller(self, num):
        if num > self.tot:
            return (self.n - 1, self.tot)
        note = -1
        tmp = 0
        for power in self.powers:
            if note + power >= self.n or tmp + self.bit[note + power] >= num:
                continue
            note += power
            tmp += self.bit[note]
        return (note, tmp)

def main():
    (n, q) = MII()
    nums = LII()
    fen = FenwickTree(nums)
    for _ in range(q):
        (i, x) = MII()
        i -= 1
        fen.add(i, x - nums[i])
        nums[i] = x
        if nums[0] == 0:
            print(1)
            continue
        idx = 0
        cur = nums[0]
        ans = -2
        while True:
            (idx, ncur) = fen.bisect_max_smaller(cur * 2)
            idx += 1
            if idx == n:
                break
            if ncur == nums[idx]:
                ans = idx
                break
            cur = ncur + nums[idx]
        print(ans + 1)
    return
t = 1
for _ in range(t):
    main()

Solution (Python):
import heapq
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_sum0(i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s

def get_sum(s, t):
    ans = 0 if s > t else get_sum0(t) - get_sum0(s - 1)
    return ans

def add(i, x):
    while i < len(tree):
        tree[i] += x
        i += i & -i
(n, q) = map(int, input().split())
a = [0] + list(map(int, input().split()))
h = [[] for _ in range(31)]
for i in range(1, n + 1):
    heapq.heappush(h[a[i].bit_length()], i)
tree = [0] * (n + 1)
for i in range(1, n + 1):
    tree[i] += a[i]
    j = i + (i & -i)
    if j < len(tree):
        tree[j] += tree[i]
u = [-1] * (n + 1)
c = [0] * (n + 1)
for i in range(31):
    hi = h[i]
    if not len(hi):
        continue
    j = heapq.heappop(hi)
    (u[j], c[j]) = (0, get_sum0(j - 1))
    if not len(hi):
        heapq.heappush(hi, j)
        continue
    k = hi[0]
    (u[k], c[k]) = (0, get_sum0(k - 1))
    heapq.heappush(hi, j)
ans = []
inf = pow(10, 9) + 1
for z in range(q):
    (p, x) = map(int, input().split())
    d = x - a[p]
    a[p] = x
    if len(ans) and (not d):
        ans0 = ans[-1]
        ans.append(ans0)
        continue
    add(p, d)
    heapq.heappush(h[x.bit_length()], p)
    ans0 = inf
    for i in range(31):
        hi = h[i]
        while hi and a[hi[0]].bit_length() ^ i:
            heapq.heappop(hi)
        if not len(hi):
            continue
        j = heapq.heappop(hi)
        if u[j] == z:
            s = c[j] if j <= p else c[j] + d
        else:
            s = get_sum0(j - 1)
        (u[j], c[j]) = (z, s)
        if s == a[j]:
            ans0 = min(ans0, j)
        while hi and (a[hi[0]].bit_length() ^ i or j == hi[0]):
            heapq.heappop(hi)
        if not len(hi):
            heapq.heappush(hi, j)
            continue
        k = hi[0]
        if u[k] == z:
            s = c[k] if k <= p else c[k] + d
        else:
            s = get_sum0(k - 1)
        (u[k], c[k]) = (z, s)
        if s == a[k]:
            ans0 = min(ans0, k)
        heapq.heappush(hi, j)
    ans0 = (ans0 + 1) % (inf + 1) - 1
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))