「CSP-J/S2022模拟赛7.17 D」函数
给定一个长度为 n 的数组 A, 定义一个二元函数 f(x, y), 1 leq x leq 10^{9}, 1 leq y leq n :
你需要回答 q 个询问, 每个询问给出两个数 x_{i}, y_{i}, 你需要求出 fleft(x_{i}, y_{i}right) 的值。
1leq n,qleq 5times 10^5,1leq x_ileq 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
代码语言：javascript复制#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 '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;
}
