我们把这道题手上的式子转化一下:令负数前缀和为,正数前缀和为。
所以有:
其中都是随着的选择不断变换的。这道题就变成了选择一个,最大化/最小化这种形式,每次询问单独给出。有一道类似的题:SCOI2019-湖之精灵的游戏。
把这个式子变一下形式:,目标是让b最大/最小。我们发现这个式子的几何意义就是用一个斜率为的直线去切一个凸包,直线的最大/最小截距是多少。所以可以直接建凸包二分。
/*
_|_| _| _| _|
_| _| _| _|_| _|_|_|_| _| _| _|
_| _| _|_| _| _| _|_|
_| _| _| _| _| _| _| _|
_|_| _| _|_|_|_| _|_| _| _|
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
//#define ls (rt<<1)
//#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
typedef long double ldb;
#define int long long
using namespace std;
const ldb eps=1e-13;
const int maxn=50105;
const int gg=1000;
const int inf=1e9+100;
int a[maxn];
int bl[maxn];
int debug=0;
ll N,P;
struct BIT{
ll c[maxn];
void add(int loc,int val){for(int i=loc;i<maxn;i+=i&-i)c[i]+=val;}
ll query(int loc)
{
ll ans=0;for(int i=loc;i;i-=i&-i)ans+=c[i];return ans;}
}po,na;
struct convex{
int num[gg],cnt,stk[gg],top,base;
pair<ll,ll> val[gg];
convex(){cnt=0;}
void ins(int x){
num[++cnt]=x;
if(a[x]>0)P+=a[x],po.add(x,a[x]);
else N+=-a[x],na.add(x,-a[x]);
}
ldb slope(int a,int b){
if(val[a].fi==val[b].fi){
if(val[a].se>val[b].se)return -1e18;
else return 1e18;
}
return 1.0*(val[a].se-val[b].se)/(val[a].fi-val[b].fi);}
void insertp(int idx){
if(debug)cout<<"add point: "<<idx+num[1]-1<<" ("<<val[idx].fi<<","<<val[idx].se<<")"<<endl;
while(top>=2&&slope(stk[top],idx)>slope(stk[top-1],stk[top])+eps)top--;
stk[++top]=idx;
}
void build(){
if(debug)cout<<"Rebuilding..."<<endl;
base=num[1]-1;
if(num[1]==0){
int jk=1;
}
ll prep=po.query(num[1]-1),pren=na.query(num[1]-1);
top=0;
rep(i,1,cnt){
int x=num[i];
if(a[x]>0)prep+=a[x];
else pren+=-a[x];
val[i]=mk(pren,prep);insertp(i);
}
//for(int i=cnt;i>=1;i--)insertp(i);
}
int query(ldb k){
int l=1,r=top;
while(l<r){
int mid=(l+r)>>1;
if(slope(stk[mid],stk[mid+1])>k+eps)l=mid+1;
else r=mid;
}
return stk[l]+base;
}
}part[gg];
int cnt;int n,m;
int q(){
ldb ans=-1e18,loc=-1;ldb k=(ldb)(P)/N;if(debug)cout<<"Searching.... k is "<<k<<endl;
rep(i,1,cnt){
int idx=part[i].query(k);
ll prep=po.query(idx),pren=na.query(idx);
ldb tmp=(ldb)(prep)/(P)-(ldb)(pren)/(N);
if(debug)cout<<"Ans in block "<<i<<" is:"<<tmp<<endl;
// if(fabs(ans-tmp)<eps)continue;
// else
if(tmp>ans+eps){
ans=tmp;loc=idx;
}
}
while(loc>1){
ll prep=po.query(loc),pren=na.query(loc);
ldb tmp1=(ldb)(prep)/(P)-(ldb)(pren)/(N);
prep=po.query(loc-1),pren=na.query(loc-1);
ldb tmp2=(ldb)(prep)/(P)-(ldb)(pren)/(N);
if(tmp2+eps>tmp1)loc--;
else break;
}
while(loc<n){
ll prep=po.query(loc),pren=na.query(loc);
ldb tmp1=(ldb)(prep)/(P)-(ldb)(pren)/(N);
prep=po.query(loc+1),pren=na.query(loc+1);
ldb tmp2=(ldb)(prep)/(P)-(ldb)(pren)/(N);
if(tmp2>tmp1+eps)loc++;
else break;
}
return loc;
}
signed main(){
freopen("joker.in","r",stdin);
freopen("joker.out","w",stdout);
scanf("%lld%lld",&n,&m);
int bk=sqrt(n);
rep(i,1,n)scanf("%lld",&a[i]);
rep(i,1,n)bl[i]=i/bk+1;cnt=n/bk+1;
rep(i,1,n)part[bl[i]].ins(i);
rep(i,1,cnt)if(part[i].cnt)part[i].build();
printf("%lld\n",q());
rep(i,1,m){
int p,v;scanf("%lld%lld",&p,&v);
if(a[p]>0)po.add(p,-a[p]),P+=-a[p];
else na.add(p,a[p]),N+=a[p];
a[p]=v;
if(a[p]>0)po.add(p,a[p]),P+=a[p];
else na.add(p,-a[p]),N+=-a[p];
part[bl[p]].build();
printf("%lld\n",q());
}
return 0;
}