P7028 [NWRRC2017]Joker - 凸包最值问题

我们把这道题手上的式子转化一下：令负数前缀和为$x$，正数前缀和为$y$。
所以有：

$ans=\frac{P}{y}+\frac{N}{x}$

其中$x,y$都是随着$i$的选择不断变换的。这道题就变成了选择一个$i$，最大化/最小化$kx_i+by_i$这种形式，每次询问$k,b$单独给出。有一道类似的题：SCOI2019-湖之精灵的游戏。
把这个式子变一下形式：$y_i=kx_i+b$，目标是让b最大/最小。我们发现这个式子的几何意义就是用一个斜率为$k$的直线去切一个凸包，直线的最大/最小截距是多少。所以可以直接建凸包二分。

/*
                                                  
  _|_|                              _|  _|    _|  
_|    _|  _|  _|_|  _|_|_|_|        _|  _|  _|    
_|    _|  _|_|          _|          _|  _|_|      
_|    _|  _|          _|      _|    _|  _|  _|    
  _|_|    _|        _|_|_|_|    _|_|    _|    _|  
                                                                                                    
*/ 
#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;
}