自动搬运

查看原文

来自洛谷，原作者为

	SnowTrace 要信自己的感觉够真

搬运于2025-08-24 23:09:25，当前版本为作者最后更新于2025-02-05 22:05:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

场上奋战两个半小时，最后二十分钟推出来性质，最后获得零分。

这个题要你刻画的是若干个绝对值函数的加和的性质。

我们把问题变成维护一个一开始全为 0 的序列 $b$，每次给序列 $b$ 加上一个绝对值函数，问需要多少次使得 $\forall i,b_i\geq a_i$。

既然刻画不明白，我们先考虑一些简单的性质。首先我们可以发现一件事情是你操作不同的位置，对 $\sum b_i$ 的贡献是不同的，具体来说，操作位置 $1$ 和 $n$ 能使序列 $b$ 的和单次增加最多。

然后你发现如果同时在 $1$ 和 $n$ 上做操作相当于给每个 $b_i$ 都加上 $n-1$，从而我们可以使用这个策略通过 sub1，容易证明这是最优的。

继续观察。注意到如果你同时选了 $i$ 和 $n-i$，这个操作肯定不如选 $1$ 和 $n$，所以我们得到结论 $i$ 和 $n-i$ 不能同时选。

很可惜这个结论没有用，但是令人惊讶的是这个结论是可以推广的，具体来说，如果你操作了两个位置 $1<x<y<n$，你不如操作 $x-1$ 和 $y+1$。

由此归纳出一个结论：在最优解中一定是选了若干个 $1$，若干个 $n$，和一个其他位置。证明考虑假如现在有两个不为 $1$ 或 $n$ 的位置，一定可以通过上面的变化把其中一个变成 $1$ 或 $n$）

问题变成下面这个形式，设 $1$ 操作了 $x$ 次，$n$ 操作了 $y$ 次，还在位置 $m$ 选了一个数，则有限制 $\forall i,ix+(n-i)y+|m-i|\geq a_i$，你需要最小化 $x+y$ 的值。

我们先考虑暴力是怎么做，首先枚举一个 $m$，因为我们要求的是 $x+y$ 的最小值，把 $x+y$ 提出来处理，然后就可以二分答案，既 $(x+y)(n-i)+(2i-n)x+|m-i|\geq a_i$，可以对其二分，会得到若干对 $x$ 的限制，时间复杂度 $O(n^2\log V)$。

接下来我们观察到第二个性质：如果规定只能操作 $1$ 和 $n$，得到的答案最多比最优解多 1。

这个结论是显然的，因为选择的 $m$ 显然可以用一个 $1$ 和一个 $n$ 代替，从而可以取到 $ans+1$。

我们可以先二分答案求出来只用 $1$ 和 $n$ 时的答案，设为 $ans$，接下来我们只需要判断 $ans-1$ 是否能被取到。

我们希望对于不同的 $m$ 同时维护 check 的结果。可以先把式子列出来，不妨设 $2i \geq n$，则需要 $x \geq \dfrac{a_i+(x+y)(n-i)+|m-i|}{2i-n}$，由于我们需要 check 的答案固定，所以右边其实是个常数。

接下来考虑 $m$ 改变对这个式子的影响，注意到对于一个 $i$，$|m-i|$ 的变化量是 $O(n)$ 的，所以实际上右边式子的值只会改变 $O(\dfrac{n}{2i-n})$ 次，这是可以维护的。

具体来说我们可以用一个优先队列维护当前最严格的限制，这样做时间复杂度是 $O(n\log n\log V)$ 的，但是注意到操作是 $O(n\log n)$ 次区间取 $\max$，只需要在最后输出每个位置的值，可以使用猫树优化，这样时间复杂度是 $O(n\log V)$ 的。

实际上 $2i-n$ 可以是一个负数，也可以是 0，需要特判。

代码正在赶工中，因为负数除负数上下取整实在写不明白了。

upd on 2.6: 奋战四个小时终于把代码写出来了，感觉其实和季风差不多，但是写不明白啊。

//非常优美的题，但是代码太毒瘤了 
#include<bits/stdc++.h>
using namespace std;
#define int long long
int Abs(__int128 x){if(x<0)return -x;return x;}
__int128 chu(__int128 x,int y){
	//向上取整
	return (x+y-1)/y;
}
__int128 Chu(__int128 x,int y){
	//向下取整
	if(x<=0 and y<0)return (-x)/(-y);
 	else return -1;
}
int n;
__int128 a[500005];int b[500005];
bool check(__int128 x){
	__int128 L = 0,R = x;
	for(int i = 0;i<=n;i++){
		if(2*i == n){
			if(x*(n-i)<a[i])return 0;
			continue;
		}
		if(2*i<n){
			//是一个负数
			__int128 C = a[i]-(n-i)*x;
			R = min(R,Chu(C,2*i-n)); 
		}else{
			__int128 C = a[i]-(n-i)*x;
			L = max(L,chu(C,2*i-n));
		}
	}
	return (L<=R);
}
struct heap{
	priority_queue<int,vector<int>,greater<int> >q,del;
	void clear(){while(q.size())q.pop();while(del.size())del.pop();}
	void Delete(int x){del.push(x);}
	void Insert(int x){q.push(x);}
	int top(){
		while(del.size() and q.top() == del.top())q.pop(),del.pop();
		return q.top();
	}
}ql,qr;
vector<int>addl[500005],dell[500005],addr[500005],delr[500005];
void Addl(int l,int r,int x,int id){
	//给一段区间加上 x 的限制
	addl[l].push_back(-x),dell[r+1].push_back(-x); 
}
void Addr(int l,int r,int x,int id){
	addr[l].push_back(x),delr[r+1].push_back(x);
}

int work(int X){
	ql.clear(),qr.clear();
	ql.Insert(0),qr.Insert(X);
	for(int i =0;i<=n+1;i++)addl[i].clear(),dell[i].clear(),addr[i].clear(),delr[i].clear();
	int i = n;
	for(int i = 0;i<=n;i++)a[i] -= (n-i)*X; 
	while(2*i>n){
		// n-2i
		int now = i;
		while(now<=n){
			// (0,a] 算一段
			//算出和这个点值相同的最远的点
			__int128 C = a[i]-abs(now-i),to = 0;
			//对于更远的点 C 的数值会减小
			if(C<=0){
				to = 0;
			}else{
				to = C/(2*i-n)*(2*i-n)+1;
				if(C%(2*i-n) == 0)to = C-(2*i-n)+1;
			}
			int r = min(Abs(to-C)+now,n);
		
			if(C>0){
				Addl(now,r,chu(C,i*2-n),i);
			}
			now = r+1;
		}
		now = i-1;
		while(now>=0){
			__int128 C = a[i]-abs(now-i),to = 0;
			if(C<=0){
				to = 0;
			}else{
				to = C/(n-2*i)*(n-2*i)+1;
				if(C%(2*i-n) == 0)to = C-(2*i-n)+1;
			} 
			int l = max(now-Abs(to-C),0ll);
			if(C>0){
				Addl(l,now,chu(C,i*2-n),i);
			}
			now = l-1;
		}
		--i;
	}
	i = 0;
	while(2*i<n){
		int now = i;
		while(now<=n){
			__int128 C = a[i]-abs(now-i),to = 0;
			if(C<=0){
				to = -C;
				if(to%(n-2*i)!=0)to += (n-2*i)-to%(n-2*i);
				else to += (n-2*i);
				--to;
				to = -to;
			}else{
				to = 0;
			}
			int r = min(Abs(to-C)+now,n);
			if(C>0)Addr(now,r,-1,i);
			else Addr(now,r,Chu(C,i*2-n),i);
			now = r+1;
		}
		now = i-1;
		while(now>=0){
			__int128 C = a[i]-abs(now-i),to = 0;
			if(C<=0){
				to = -C;
				if(to%(n-2*i)!=0)to += (n-2*i)-to%(n-2*i);
				else to += (n-2*i);
				--to;
				to = -to;
			}else{
				to = 0;
			}
			int l = max(now-Abs(to-C),0ll);
			if(C>0)Addr(l,now,-1,i);
			else Addr(l,now,Chu(C,i*2-n),i);
			now = l-1; 
		}
		++i;
	}
	for(int i = 0;i<=n;i++){
		for(auto x:addl[i])ql.Insert(x);
		for(auto x:dell[i])ql.Delete(x);
		for(auto x:addr[i])qr.Insert(x);
		for(auto x:delr[i])qr.Delete(x);
		if(n%2 == 0 and (a[n/2]-abs(n/2-i))>0)continue;
		int L = -ql.top(),R = qr.top();
		if(L<=R)return 1;
	}
	return 0;
}
void solve(){
	cin >> n;--n;
	for(int i = 0;i<=n;i++)cin >> b[i];for(int i = 0;i<=n;i++)a[i] = b[i];
	__int128 sum = 0;int mx = 0;for(int i = 0;i<=n;i++)sum += b[i],mx = max(mx,b[i]);
	int l = sum/n/n,r = 2*(mx+n-1)/n;
	while(l<r){
		int mid = l+r>>1;
		if(check(mid))r = mid;
		else l = mid+1;
	}
	int ans = r;
	if(ans>1 and work(ans-2))--ans;
	cout << ans << '\n';
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t;cin >> t;;
	while(t--)solve();
	return 0;
}/*
*/