Description：

给一个数列，支持单点修改，询问第一个满足 $presum[i-1]=a[i]$ 的位置。

$1\le n \le 200000,1\le a[i]\le 10^9$

Solution：

k]建一棵线段树，维护区间和和区间最大值，修改直接单点修改，查询时，先把光标定在第 $0$ 位，把 $pre$ 设为第 $0$ 位的前缀和，然后查询第一个值大于 $pre$ 的位置 $k$ ，如果这个位置满足 $presum[k]=2\times a[k]$ ，那么就找到了，否则把光标定在 $k$ ， $pre$ 设为第 $k$ 位，再查询第一个前缀和大于 $pre$ 的位置 $k$ ，一直到找到或者 $cur \ge n$ 。

这种做法看似十分暴力。但是由于序列中所有元素 $\le 10^9$ ，而每一次操作都找到了一个值大于 $pre$ 的点，也就说 $pre$ 每次至少翻一倍，所以这个做法的复杂度是 $log$ 的，卡一卡常就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#pragma GCC optimize(2)

using namespace std;

int n,m;

#define MAXN 800010

typedef long long ll;

ll a[MAXN];

struct node

{

	int lc,rc;

	ll mx;

	ll sum;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r){t[rt].sum = t[rt].mx = a[l];return;}

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	t[rt].sum = t[t[rt].lc].sum + t[t[rt].rc].sum;

	t[rt].mx = max(t[t[rt].lc].mx,t[t[rt].rc].mx);

	return;

}

void modify(int rt,int p,ll k,int l,int r)

{

	if(l == r)

	{

		t[rt].sum = t[rt].mx = a[l] = k;;

		return;

	}

	if(p <= mid)modify(t[rt].lc,p,k,l,mid);

	else modify(t[rt].rc,p,k,mid + 1,r);

	t[rt].sum = t[t[rt].lc].sum + t[t[rt].rc].sum;

	t[rt].mx = max(t[t[rt].lc].mx,t[t[rt].rc].mx);

	return;

}

ll querysum(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].sum;

	register ll res = 0;

	if(L <= mid)res += querysum(t[rt].lc,L,R,l,mid);

	if(R > mid)res += querysum(t[rt].rc,L,R,mid + 1,r);

	return res;

}

int query(int rt,int L,int R,int l,int r,ll x)

{

	if(L <= l && r <= R)

	{

		if(t[rt].mx < x)return -1;

		if(l == r)return l;

		if(t[t[rt].lc].mx > x)return query(t[rt].lc,L,R,l,mid,x);

		else query(t[rt].rc,L,R,mid + 1,r,x); 

	}

	register int ans = -1;

	if(L <= mid)ans = query(t[rt].lc,L,R,l,mid,x);

	if(ans != -1)return ans;

	else return query(t[rt].rc,L,R,mid + 1,r,x);

}

inline ll read()

{

	register ll res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int main()

{

	freopen("challenge.in","r",stdin);

	freopen("challenge.out","w",stdout);

	scanf("%d%d",&n,&m);

	for(register int i = 1;i <= n;++i)a[i] = read();

	build(root,1,n);

	register int p;

	register ll k;

	for(int i = 1;i <= m;++i)

	{

		p = read();k = read();

		modify(root,p,k,1,n);

		register int cur = 0,res = -1;

		register ll pre = 0;

		while(cur < n)

		{

			register int tmp = query(root,cur + 1,n,1,n,pre);

			if(tmp == -1)break;

			cur = tmp;

			pre = querysum(root,1,tmp,1,n);

			if(pre - a[tmp] == a[tmp])

			{

				res = tmp;

				break;

			}

		}

		printf("%d\n",res);

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}