Nastya and King-Shamans
Contest: Codeforces Round 489 (Div. 2)
Difficulty rating: 2500
Tags: binary search, data structures

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 format:
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 format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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.

Example input:
2 1
1 3
1 2

Example output:
-1

Example input:
3 4
2 2 3
1 1
1 2
2 4
3 6

Example output:
3
2
-1
3

Editorial:
This problem was inspired by idea which was offered by my unbelievable girlfriend :)
Solution I
In this problem we maintain two segment trees - with maximum and with sum. After every query we recalculate these trees in $${\mathcal{O}}(\log N)$$ for a query. Now we only have to understand, how to answer for a query? Let's call a prefix of the array as good in the case if we surely know that it doesn't contain a king-shaman. So either the first shaman is king and we are able to answer for the query, or we call the prefix with length 1 as good. Then let's repeat the following operation:
• We call $${\hat{p}}_{i}$$ as sum in the good prefix now. We find it using the segment tree with sums.
• We find the leftmost element which may be king-shaman yet. We can realise that it's the leftmost element, which doesn't lie in the good prefix (as there isn't king-shaman according the definition), which have a value at least $${\hat{p}}_{i}$$. It can be done using segment tree with maximums, with descent.
• We check if this found shaman is king. If isn't, we can say that the good prefix finishes in this shaman now, because it was the leftmost shaman who might be king.
Every operation works in $${\mathcal{O}}(\log N)$$. Let's notice, that one operation increases sum in the good prefix at least by two times. So, after $${\mathcal{O}}(\log \operatorname* { M a x } ( A _ { i } ) )$$ operations sum in the good prefix will become more than a maximal possible number in the array, so that we will be able to finish, because we will be sure that answer will be -1. Complexity of the solution is $${ \mathcal { O } } ( N \cdot \log N \cdot \log \operatorname* { M a x } ( a _ { i } ) )$$.
Solution II
Let pi be the prefix sums of a. We're gonna introduce fi = pi - 2·ai and reformulate the queries using these new terms.
1. Imagine we wanna change the value at j to val. Let δ = val - aj. Then fj will decrease by δ whereas fi > j will increase by δ.
2. Imagine we wanna find the answer. Then it's sufficient to find any i satisfying fi = 0.
Split f into blocks of size M. Each block will be comprised of pairs (fi, i) sorted by f. At the same time we will maintain overhead array responsible for lazy additions to blocks. How does this help?
1. Let b = j / M. The goal is to find the position of j, decrease its value and increase values for all i > j within this block. It can be done in a smart way in O(M) (actually, this can be represented as merging sorted vectors). You should also take care of the tail, i.e add δ to overheadj > b in O(n / M) time.
2. We're asked to find such i that fi + overheadj / M = 0. All blocks are sorted, thus we can simply apply binary search in $${ \mathcal { O } } \left( ( n / M ) \cdot \log M \right)$$ overall.
The optimal assignment is $$M = \sqrt{n} \log n$$ which results into $$O(q\sqrt{n}\log n)$$ total runtime.
The huge advantage of this approach is its independency from constraints on a (i.e non-negativity). Although we didn't succeed in squeezing this into TL :)
Solution III
Group the numbers according to their highest bits (with groups of the form [2k... 2k + 1] and separately for zeros). Inside each groups (no more than $$\log 10^9$$ of them) we maintain elements in increasing order of indexes.
It's easy to see that each group contains no more than two candidates for answer (since their sum is guaranteed to be greater than any of the remaining ones). This observation leads to an easy solution in $${\mathcal {O}}(q\log n\log 10^{9})$$ — we iterate over groups and check prefix sums for these candidates.
There's actually further space for optimizations. Let's maintain prefix sums for our candidates — this allows us to get rid of the extra log when quering the tree. Almost everything we need at this step is to somehow process additions and deletions — change the order inside two blocks and probably recalculate prefix sums. The only thing left is to stay aware of prefix sum changes for the remaining blocks. Luckily, they can be fixed in O(1) per block (if i > j then the sum increases by val - aj and stays the same otherwise).
The resulting comlexity is $$O(q \cdot (\log 10^9 + \log n))$$.