题目描述

Joker prepares a new card trick with a strong mathematical background. You are asked to help Joker with calculations.

There is a row of $n$ cards with non-zero numbers $a_{i}$ written on them. Let's call the sum of all positive numbers $P$ and the sum of all negative numbers $N$ . Every card $i$ has a weight $w_{i} = a_{i}/P$ if $a_{i} > 0$ and $a_{i}/|N|$ otherwise.

Let's denote $s_{i} = ( \sum_{j=1}^{j \le i}{w_j})$. Joker needs to know positive $i$ with the largest $s_{i}.$ If there is more than one such $i$ , he is interested in the smallest one.

But static tricks are boring, so Joker wants to change numbers on some cards, and after each change he needs to known where is the largest $s_{i}$ is.

输入格式

The first line of the input contains two integers $n$ and $m$ -- the number of cards and the number of changes $(1 \le n , m \le 50 000)$ .

The second line consists of $n$ integers $a_{i}$ -- numbers written on cards at the beginning $(−10^{9} \le a_{i} \le 10^{9}; a_{i} ≠ 0)$ .

The following $m$ lines contain two integers each: $p_{i}$ and $v_{i},$ that means value of card at position $p_{i}$ is changed to $v_{i} (1 \le p_{i} \le n$ ; $−10^{9} \le v_{i} \le 10^{9}; v_{i} ≠ 0)$ .

It is guaranteed that at each moment there is at least one card with positive number and at least one card with negative number. The sum of all positive cards will never exceed $10^{9}$ and the sum of all negative cards will never exceed $−10^{9}.$

输出格式

You should output $m+1$ integers. The first integer is the position of the largest $s_{i}$ for the initial numbers. Next $m$ numbers are positions of the largest $s_{i}$ after each change.

题目大意

有一个长度为 $n$ 的数列，第 $i$ 个元素的值为 $a_i$，定义 $P$ 为数列中所有正整数的和，$N$ 为所有负整数的和。定义一个元素的重要值 $w_i=\begin{cases}\dfrac{a_i}{P}&a_i>0\\\dfrac{a_i}{|N|}&\text{otherwise}\end{cases}$，并定义 $s_i$ 为前 $i$ 个元素的重要值之和，即 $\sum\limits_{j=1}^iw_j$。

请先求出当前数列中使 $s_i$ 最大的 $i$。然后有 $m$ 次操作，每次操作将某个元素改成一个给定的值，请在每次操作后求出当数列中使 $s_i$ 最大的 $i$。

如果有多个满足要求的 $i$，则答案取最小的。

Translated by Eason_AC
2020.11.15

4 7
1 -5 3 -5
4 -1
2 -1
3 10
4 10
1 -1
2 1
3 -1

3
1
3
3
1
4
4
4

提示

Time limit: 3 s, Memory limit: 512 MB.