在学校OJ上过了，luogu 没过

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
const double eps=1e-15;
ll a[50010],pos[50010],L[50010],R[50010],klen,ksum,P,Q;
pair<ll,ll>p[50010];
deque<ll>q[50010];
ll x(ll i)
{
	return p[i].first;
}
ll y(ll i)
{
	return p[i].second;
}
void build(ll l,ll r,ll id)
{
	q[id].clear();
	ll sx=0,sy=0;
	for(ll i=l;i<=r;i++)
	{
		sx+=(a[i]>=0)*a[i];
		sy+=(a[i]<0)*a[i];
		p[i]=make_pair(sx,sy);
		while(q[id].size()>=2&&(y(q[id][q[id].size()-2])-y(q[id].back()))*(x(q[id].back())-x(i))<=(y(q[id].back())-y(i))*(x(q[id][q[id].size()-2])-x(q[id].back())))
		{
			q[id].pop_back();
		}
		q[id].push_back(i);
	}
}
bool check(ll mid,ll id)
{
	return (y(q[id][mid+1])-y(q[id][mid]))*P>=Q*(x(q[id][mid+1])-x(q[id][mid]));
}
ll divide_search(ll id)
{
	ll l=0,r=q[id].size()-1,mid,ans=0;
	while(l<r)
	{
		mid=(l+r)/2;
		if(check(mid,id)==true)
		{
			ans=mid+1;
			l=mid+1;
		}
		else
		{
			r=mid;
		}
	}
	return q[id][ans];
}
void init(ll n)
{
	klen=sqrt(n*log2(n));
	ksum=n/klen;
	for(ll i=1;i<=ksum;i++)
	{
		L[i]=R[i-1]+1;
		R[i]=R[i-1]+klen;
	}
	if(R[ksum]<n)
	{
		ksum++;
		L[ksum]=R[ksum-1]+1;
		R[ksum]=n;
	}
	for(ll i=1;i<=ksum;i++)
	{
		for(ll j=L[i];j<=R[i];j++)
		{
			pos[j]=i;
		}
		build(L[i],R[i],i);
	}
}
void update(ll x,ll y)
{
	P-=(a[x]>=0)*a[x];
	Q-=(a[x]<0)*a[x];
	a[x]=y;
	P+=(a[x]>=0)*a[x];
	Q+=(a[x]<0)*a[x];
	build(L[pos[x]],R[pos[x]],pos[x]);
}
ll query()
{
	ll id=0,sum=0,sx=0,sy=0;
	double ans=-0x7f7f7f7f;
	for(ll i=1;i<=ksum;i++)
	{
		sum=divide_search(i);
		if(1.0*(p[sum].first+sx)/P-1.0*(p[sum].second+sy)/Q-ans>eps)
		{
			ans=1.0*(p[sum].first+sx)/P-1.0*(p[sum].second+sy)/Q;
			id=sum;
		}
		sx+=p[R[i]].first;
		sy+=p[R[i]].second;
	}
	return id;
}
int main()
{
	ll n,m,x,y,i;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		P+=(a[i]>=0)*a[i];
		Q+=(a[i]<0)*a[i];
	}
	init(n);
	cout<<query()<<endl;
	for(i=1;i<=m;i++)
	{
		cin>>x>>y;
		update(x,y);
		cout<<query()<<endl;
	}
	return 0;
}