当前位置: 首页 > news >正文

题解:P13523 [KOI 2025 #2] 序列与查询

题目:

长度相同的子段受 \(x\) 影响相同。

哇好厉害的性质,可以直接把每个长度的最大子段和跑下来,询问 \(X\) 相当于找 \(val_{len}+len×X\) 最大的 \(len\),预处理 \(O(n^2+qn)\),查询优化?

考虑画到坐标轴上,把 \((len,val_{len})\) 看成一个点,画一个 \(y=Xx\) 的直线,发现每个点的答案其实是纵坐标加上横坐标在 \(y=kx\) 的值。

凭借小学数学,敏锐地再画一个 \(y=-Xx\) 的直线,这样每个点的答案是每个点向下到直线的距离,已知直线去选最远的点,这很像凸包,简单思考一下确实是。复杂度 \(O(n^2+q\log n)\)

思考如何优化预处理的过程,序列分治上做肯定简单点,再思考怎么拼接左面的后缀和右面的前缀。

大概长这样:
\(dp_{i+j}=hz_i+qz_j\)
其中:
\(dp_i\)\(i\) 长度的最大子段和。
\(hz_i\)\([mid-i+1,mid]\) 的和。
\(qz_j\)\([mid+1,mid+1+j-1]\) 的和。

闵可夫斯基和优化,把 \(hz\)\(qz\) 的凸包维护出来,然后合并后更新 \(dp\),复杂度 \(O(n\log n+q\log n)\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read()
{int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return x*f;
}
const int QAQ=1e6+7,inf=1e17+7;
int n,q,a[QAQ],x[QAQ],d[QAQ],cnt,o1,o2,o3;
struct xxx {int x,y;} tb[QAQ],zb[QAQ],yb[QAQ],he[QAQ];
double xie(xxx a,xxx b) {return 1.0*(b.y-a.y)/(b.x-a.x);}
xxx operator +(xxx a,xxx b) {return {a.x+b.x,a.y+b.y};}
xxx operator -(xxx a,xxx b) {return {a.x-b.x,a.y-b.y};}
void chuli(int l,int r)
{if(l==r) return d[1]=max(d[1],a[l]),void();int mid=(l+r)>>1;chuli(l,mid),chuli(mid+1,r);o1=o2=0;int sum=0;for(int i=mid;i>=l;i--){sum+=a[i];xxx nw={mid-i+1,sum};while(o1&&xie(zb[o1-1],zb[o1])<xie(zb[o1-1],nw)) o1--;zb[++o1]=nw;}sum=0;for(int i=mid+1;i<=r;i++){sum+=a[i];xxx nw={i-(mid+1)+1,sum};while(o2&&xie(yb[o2-1],yb[o2])<xie(yb[o2-1],nw)) o2--;yb[++o2]=nw;}if(!o1){for(int i=1;i<=o2;i++) d[yb[i].x]=max(d[yb[i].x],yb[i].y);return ;}if(!o2){for(int i=1;i<=o1;i++) d[zb[i].x]=max(d[zb[i].x],zb[i].y);return ;}o3=0;he[++o3]=zb[1]+yb[1];for(int i=o1;i>1;i--) zb[i]=zb[i]-zb[i-1];for(int i=o2;i>1;i--) yb[i]=yb[i]-yb[i-1];int ccx=2,swl=2;while(ccx<=o1&&swl<=o2){if(atan2(1.0*zb[ccx].y,1.0*zb[ccx].x)>=atan2(1.0*yb[swl].y,1.0*yb[swl].x))he[++o3]=zb[ccx],ccx++;else he[++o3]=yb[swl],swl++;}while(ccx<=o1) he[++o3]=zb[ccx],ccx++;while(swl<=o2) he[++o3]=yb[swl],swl++;for(int i=2;i<=o3;i++) he[i]=he[i]+he[i-1];for(int i=1;i<=o3;i++) d[he[i].x]=max(d[he[i].x],he[i].y);
}
signed main()
{cin>>n>>q;for(int i=1;i<=n;i++) a[i]=read(),d[i]=-inf;chuli(1,n);tb[0]={0,-inf};for(int i=1;i<=n;i++){xxx nw={i,d[i]};while(cnt&&xie(tb[cnt-1],tb[cnt])<xie(tb[cnt-1],nw)) cnt--;tb[++cnt]=nw;}for(int i=1,x;i<=q;i++){x=read();int l=1,r=cnt,mid,da;double k=-x;while(l<r){ mid=(l+r)>>1;if(xie(tb[mid],tb[mid-1])<k) r=mid;else l=mid+1,da=mid;}if(xie(tb[r],tb[r-1])>=k) da=r;printf("%lld\n",tb[da].y+tb[da].x*x);}return 0;
}
http://www.hskmm.com/?act=detail&tid=18413

相关文章:

  • 2025年9月26日 - 20243867孙堃2405
  • HarmonyOS 5 网络编程与材料存储实战:从RESTful API到本地持久化
  • 老系统-新系统的数据迁移
  • C语言中的for循环
  • excell中完成矩阵的转置相乘
  • go 面试题
  • 论文笔记:How Can Recommender Systems Benefit from Large Language Models: A Survey - 详解
  • newDay04
  • 5.WPF控件---ComboBox - 实践
  • SQLserver 通过本地方式改SA密码
  • 2_2025.9.26_2
  • k8s部署Prometheus实战
  • day005
  • AI Compass前沿速览:Qwen3-Max、Mixboard、Qwen3-VL、Audio2Face、Vidu Q2 AI视频生成模型、Qwen3-LiveTranslate-全模态同传大模型
  • javaEE初阶————多线程进阶(1) - 教程
  • 软工9.26
  • 第五篇
  • 网络安全周报:AI监控工具与关键基础设施漏洞警报
  • 重链抗体(IgG2、IgG3)与传统抗体的核心区别:从结构到功能的全方位解析
  • 9.26总结
  • 重点行业数字化转型一图参透 - 智慧园区
  • RustDesk:免费开源的跨平台远程桌面解决方案
  • uniapp
  • Ext-js-即时入门-全-
  • Ext-js4-扩展开发指南-全-
  • ECMAScript6-学习指南-全-
  • JSP征婚信息实用的系统3kx16代码+源码+数据库+调试部署+开发环境
  • CSS属性
  • 基于大数据的水产品安全信息可视化分析框架【Hadoop、spark、可视化大屏、课程毕设、毕业选题、数据分析、资料爬取、数据可视化】
  • CSS值