「CSP-J/S2022模拟赛7.17 D」函数

yzxoi

发布于 2022-09-19 14:08:14

9680

发布于 2022-09-19 14:08:14

文章被收录于专栏：OI

「CSP-J/S2022模拟赛7.17 D」函数

给定一个长度为 n 的数组 A, 定义一个二元函数 f(x, y), 1 \leq x \leq 10^{9}, 1 \leq y \leq n :

f(x, y)= \begin{cases}A_{y} & x=1 \\ f(x-1, y)+A_{y} & y=1 \text { 且 } x \neq 1 \\ \min {f(x-1, y-1), f(x-1, y)}+A_{y} & \text { otherwise }\end{cases}

你需要回答 q 个询问, 每个询问给出两个数 x_{i}, y_{i}, 你需要求出 f\left(x_{i}, y_{i}\right) 的值。

1\leq n,q\leq 5\times 10^5,1\leq x_i\leq 10^9。

Tutorial

简单转换一下题意：给定一个 10^9 \times n 的网格，每个格子有个权值，第 y 列格子权值均为 A_y，每次询问从第一行 y 列开始走，走到第 x 行某个点的路径中权值总和最小值。

贪心地考虑，每次一定是从起点开始，斜着走到 A_y 较小的一列，然后一直向上走。于是我们就可以得到一个 O(nq) 的做法。

设状态 (y,i) 表示从第一行第 y 列开始走，斜着走到第 i 列的权值和最小值。每个询问即可以从某个状态转移而来，并补上向上走到第 x 行，即为 \min (\sum_{i=j+1}^y A_i) + (x-y-j) \times a[j]。

而每个状态可以表示为一个一次函数，我们需要求其最小值，因此我们只需要维护一个下凸壳即可。

将询问离线，按照 y 从小到大排序，每次加入一条直线，维护下凸壳，在下凸壳上二分即可。

O((n+q)\log n)。

Solution

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
	Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
	Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
	Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
	Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
	Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=5e5+10;
int n,q,a[N],stk[N],top;LL s[N],g[N],Ans[N];
#define pa pair<int,int>
#define mp make_pair
#define fi first
#define se second
vector<pa> Q[N];
#define pb push_back
I bool chk(CI i,CI j,CI k){return (__int128)(a[k]-a[j])*(g[j]-g[i])<=(__int128)(a[j]-a[i])*(g[k]-g[j]);}
int main(){
	RI i,x,y;for(read(n),i=1;i<=n;i++) read(a[i]);
	for(read(q),i=1;i<=q;i++) read(x,y),Q[y].pb(mp(x,i));
	for(i=1;i<=n;i++) s[i]=s[i-1]+a[i],g[i]=s[i]-1LL*a[i]*i;
	for(i=1;i<=n;i++){
		W(top&&a[i]<a[stk[top]]) top--;W(top>1&&chk(stk[top-1],stk[top],i)) top--;stk[++top]=i;
		for(auto j:Q[i]){
			RI l=1,r=top,X=top;
			#define mid (l+r>>1)
			#define V(p) (1LL*(j.fi-i)*a[stk[p]]-g[stk[p]])
			W(l<=r) V(mid+1)>=V(mid)?X=mid,r=mid-1:l=mid+1;
			Ans[j.se]=s[i]+V(X);
		}
	}for(i=1;i<=q;i++) writeln(Ans[i]);
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-07-17 ，如有侵权请联系 cloudcommunity@tencent.com 删除

min