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

(Updated: )
oi
, ,

给定一个长度为 $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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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;
}