自动搬运

查看原文

来自洛谷，原作者为

	agicy 你很懒，什么都看不到

搬运于2025-08-24 22:26:00，当前版本为作者最后更新于2021-05-29 10:21:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

本文将同步发布于：

• 洛谷博客；
• csdn；
• 博客园；
• 简书。

题目

题目链接：洛谷 P7028、gym101612J。

题意概述

有一个长度为 $n$ 的数列，第 $i$ 个元素的值为 $a_i$，其中 $a_i\neq 0$，定义 $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$ 使得

$$s_i=\max_{j=1}^n\{s_j\}$$

考虑到 $P$ 和 $|N|$ 均为正整数（若有一项是 $0$，则显然答案为 $n$），我们给等式两边同时乘上 $P\cdot |N|$，得到

$$s_i\cdot P\cdot |N|=\max_{j=1}^n\left\{s_j\cdot P\cdot |N|\right\} $$

拆开 $s_i$ 的定义式，得到

$$\sum_{k=1}^iw_k\cdot P\cdot |N|=\max_{j=1}^n\left\{\sum_{k=1}^jw_k\cdot P\cdot |N|\right\} $$

再代入 $w_i$ 的定义式，得到单个点的值为

$$\begin{aligned} &\sum_{k=1}^i\left(\frac{a_k[a_k<0]}{|N|}P|N|+\frac{a_k[a_k>0]}{P}P|N|\right)\\ =&\sum_{k=1}^i\left(a_k[a_k<0]\cdot P+a_k[a_k>0]\cdot |N|\right)\\ =&\sum_{k=1}^i\left(a_k[a_k<0]\cdot P+a_k[a_k>0]\cdot |N|\right)\\ =&\left(\sum_{a_k<0,k\leq i}^ia_k\right)\cdot P+\left(\sum_{a_k>0,k\leq i}a_k\right)\cdot|N|\\ =&-\left(\sum_{a_k<0,k\leq i}^i-a_k\right)\cdot P+\left(\sum_{a_k>0,k\leq i}a_k\right)\cdot |N|\\ =&\left(\sum_{a_k>0,k\leq i}a_k\right)\cdot |N|-\left(\sum_{a_k<0,k\leq i}^i-a_k\right)\cdot P \end{aligned} $$

图形转换

我们观察上式，不难发现它与叉积的形式类似。

我们不妨定义

$$\vec{p}_i= \begin{cases} (a_i,0),&a_i>0\\ (0,-a_i),&a_i<0 \end{cases} $$

再定义 $\overrightarrow{\texttt{sum}}_i=\sum\limits_{j=1}^i\vec{p}_j$

那么

$$\left(\sum_{a_k>0,k\leq i}a_k\right)\cdot |N|-\left(\sum_{a_k<0,k\leq i}^i-a_k\right)\cdot P $$

就可以转化为

$$\overrightarrow{\texttt{sum}}_i\times \overrightarrow{\texttt{sum}}_n $$

现在问题转化为了给定一个向量 $\overrightarrow{\texttt{sum}}_n$ 和一堆向量 $\overrightarrow{\texttt{sum}}_i$，求解其叉积的最大值。

我们不难得到，叉积的最大值一定在 $\overrightarrow{\texttt{sum}}_i$ 对应的下凸包上取到。

分析时间复杂度

现在我们需要维护一个下凸包，每次询问在凸包上二分得到答案，而每次修改我们需要暴力重构凸包。

• 询问：时间复杂度为 $\Theta(\log_2n)$；
• 修改：由于这些点的横纵坐标都具有单调性，无需排序，时间复杂度为 $\Theta(n)$。

两种操作的时间复杂度不均衡，而操作次数却相同，这提示我们用 序列分块 的方法均衡时间复杂度。

序列分块

考虑对每 $B$ 个操作分一块，每个操作只考虑自己 块内的所有向量。

根据叉积分配率 $\bold{a}\times(\bold{b}+\bold{c})=\bold{a}\times\bold{b}+\bold{a}\times\bold{c}$，我们不难得出，这样在每个块内部查询到的最大值一定是块的局部最大值。

• 修改：我们每次修改都暴力重构一个块内部的下凸包，并维护前缀和，时间复杂度 $\Theta(B+\log_2n)$；
• 查询：我们每次查询都询问所有块的局部最大值，再通过快速查询前缀和（树状数组）得到真实最大值，时间复杂度 $\Theta(\frac{q}{B}\log_2B+\frac{q}{B}\log_2n)$。

理论分析得到 $B=\sqrt{n\log_2n}$ 时复杂度最优（为了方便，视 $\log_2B$ 与 $\log_2n$ 同阶，$n$ 与 $q$ 同阶），为 $\Theta(n\sqrt{n\log_2n})$。

参考程序

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
static char buf[1<<21],*p1=buf,*p2=buf;
#define flush() (fwrite(wbuf,1,wp1,stdout),wp1=0)
#define putchar(c) (wp1==wp2&&(flush(),0),wbuf[wp1++]=c)
static char wbuf[1<<21];int wp1;const int wp2=1<<21;
inline int read(void){
	reg bool f=false;
	reg char ch=getchar();
	reg int res=0;
	while(!isdigit(ch))f|=(ch=='-'),ch=getchar();
	while(isdigit(ch))res=10*res+(ch^'0'),ch=getchar();
	return f?-res:res;
}

inline void writeln(reg int x){
	static char buf[32];
	reg int p=-1;
	if(!x) putchar('0');
	else while(x) buf[++p]=(x%10)^'0',x/=10;
	while(~p) putchar(buf[p--]);
	putchar('\n');
	return;
}

struct Vector{
	int x,y;
	inline Vector(reg int x=0,reg int y=0):x(x),y(y){
		return;
	}
	inline Vector operator+(const Vector& a)const{
		return Vector(x+a.x,y+a.y);
	}
	inline Vector operator-(const Vector& a)const{
		return Vector(x-a.x,y-a.y);
	}
	inline Vector operator-(void)const{
		return Vector(-x,-y);
	}
};

inline ll dot(const Vector& a,const Vector& b){
	return 1ll*a.x*b.x+1ll*a.y*b.y;
}

inline ll cross(const Vector& a,const Vector& b){
	return 1ll*a.x*b.y-1ll*a.y*b.x;
}

typedef Vector Point;

const int MAXN=5e4+5;
const int MAXM=5e4+5;
const ll inf=0x3f3f3f3f3f3f3f3f;

int n,m;
int a[MAXN];
int lef[MAXN],rig[MAXN],id[MAXN];

struct Node{
	int id;
	Point p;
	inline Node(reg int id,const Point& p):id(id),p(p){
		return;
	}
};

vector<Node> S[MAXN];

inline void build(reg int id){
	S[id].clear();
	Point sum(0,0);
	for(reg int i=lef[id];i<=rig[id];++i){
		if(a[i]>0)
			sum=sum+Point(a[i],0);
		else
			sum=sum+Point(0,-a[i]);
		while(S[id].size()>=2u&&cross(S[id].back().p-(S[id].end()-2)->p,sum-S[id].back().p)<0)
			S[id].pop_back();
		S[id].push_back(Node(i,sum));
	}
	return;
}

inline int query(reg int id,const Vector& p){
	reg int _l=0,_r=S[id].size()-1,_mid;
	while(_l<_r){
		_mid=(_l+_r)>>1;
		if(cross(S[id][_mid+1].p-S[id][_mid].p,p)>0)
			_l=_mid+1;
		else
			_r=_mid;
	}
	return S[id][_l].id;
}

namespace BIT{
	inline int lowbit(reg int x){
		return x&(-x);
	}
	int n;
	Vector unit[MAXN];
	inline void Init(reg int s){
		n=s;
		return;
	}
	inline void update(reg int id,const Vector& a){
		for(reg int i=id;i<=n;i+=lowbit(i))
			unit[i]=unit[i]+a;
		return;
	}
	inline Vector query(reg int id){
		Vector res;
		for(reg int i=id;i;i^=lowbit(i))
			res=res+unit[i];
		return res;
	}
}

int main(void){
	n=read(),m=read();
	for(reg int i=1;i<=n;++i)
		a[i]=read();
	BIT::Init(n);
	for(reg int i=1;i<=n;++i)
		if(a[i]>0)
			BIT::update(i,Vector(a[i],0));
		else
			BIT::update(i,Vector(0,-a[i]));
	reg int B=max(100,int(sqrt(n*log2(n)))),tot=(n+B-1)/B;
	pair<ll,int> ans=make_pair(inf,-1);
	for(reg int i=1;i<=tot;++i){
		lef[i]=(i-1)*B+1,rig[i]=min(i*B,n);
		for(reg int j=lef[i];j<=rig[i];++j)
			id[j]=i;
		build(i);
		Vector sum=BIT::query(n);
		int pos=query(i,sum);
		ans=min(ans,make_pair(-cross(BIT::query(pos),sum),pos));
	}
	writeln(ans.second);
	while(m--){
		static int p,v;
		p=read(),v=read();
		if(a[p]>0)
			BIT::update(p,-Vector(a[p],0));
		else
			BIT::update(p,-Vector(0,-a[p]));
		a[p]=v;
		if(a[p]>0)
			BIT::update(p,Vector(a[p],0));
		else
			BIT::update(p,Vector(0,-a[p]));
		build(id[p]);
		ans=make_pair(inf,-1);
		Vector sum=BIT::query(n);
		for(reg int i=1;i<=tot;++i){
			int pos=query(i,sum);
			ans=min(ans,make_pair(-cross(BIT::query(pos),sum),pos));
		}
		writeln(ans.second);
	}
	flush();
	return 0;
}