「CSP-J/S2022模拟赛7.17 D」函数
模拟 函数 CSP S2022
2023-06-13 09:12:50 时间
「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}, 你需要求出 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;
}
相关文章
- get_headers函数模拟版
- 手机怎么模拟125k卡_NFC手机能模拟门禁卡吗?
- 模拟实现strstr函数
- Python 获取窗口句柄,模拟鼠标点击
- 用最少的代码模拟gRPC四种消息交换模式
- CSP-S2022模拟赛1 10.04
- SharpImpersonation:一款基于令牌和Shellcode注入的用户模拟工具
- 模拟请求|协议复现方案
- 大规模集群仿真模拟与调度器压测方法
- 模拟实现C++中的string类(详细解析)
- [C++]日期类计算器的模拟实现
- Python使用map,reduce高阶函数模拟实现Spark的reduceByKey算子功能详解编程语言
- pinchzoom插件模拟微信客户端点击图片放大(支持触摸滑动放到缩小)详解编程语言
- PHP操作 二维数组模拟mysql函数详解编程语言
- Xshell安全终端模拟软件带激活码下载
- 《微软飞行模拟》将提供官方中文版 DirextX 12支持也会有
- Oracle函数COS聚焦应用物理定律的计算机模拟(oracle函数cos)
- PHP模拟SQLServer的两个日期处理函数
- javascript模拟Marquee文字向左均匀滚动代码
- 用js模拟JQuery的show与hide动画函数代码
- JS模拟面向对象全解(二、类型与赋值)
- php中通过curl模拟登陆discuz论坛的实现代码
- JS模拟抽奖序效果实现代码
- PHPCURL获取cookies模拟登录的方法
- phpcurl模拟post提交数据示例