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

· · 题解

凸包合并，闵可夫斯基和 板子题！

不知道官方题解在说什么

要不是模板是黑的不然真想降蓝了

题意：给定长为 n 的序列 a，q 次询问 x，求全局 +x 的最大非空子段和。

n,q\le 10^6,|a_i|,|x|\le 10^9

记 a 的前缀和为 A。

子段和 s(l,r)=A_r-A_{l-1}+(r-l+1)x。

你发现记 S=\{(r-l,A_r-A_l):0\le l<r\le n\}，则我们要求：\max\limits_{(u,v)\in S} (ux+v)

这东西相当于求 S 的上凸包，然后二分斜率即可。

求出凸包后查询是 \mathcal{O}(q\log n) 的。

难点在于如何求凸包。

对于 l<r 的条件我们分治。

记 solve(L,R) 表示我们现在要求解 L\le l<r\le R 的 S，M 表示 mid。

我们显然先递归 solve(L,M),solve(M+1,R)。

然后考虑跨过中点的贡献。

T(L,M,R)=\{(q-p,A_q-A_p):p\in[L,M],q\in [M+1,R]\}

这样我们就把左右分离开来了，具体的：

T(L,M,R)=F(L,M)+G(M+1,R) \\ F(L,M)=\{(-p,-A_p):p\in[L,M]\} \\ G(M+1,R)=\{(q,A_q):q\in [M+1,R]\}

加法是闵可夫斯基和，于是我们递归的时候，顺便递归求解 F,G 即可。

具体的，归并式按 x 坐标排序，插入 x 的时候叉乘判断是否要把当前上凸包尾巴扔掉即可。

inline bll operator*(P x,P y){return (bll)x.X*y.Y-(bll)x.Y*y.X;}
inline bll cr(P A,P B,P C){return (B-A)*(C-A);}
inline void ins(vp &x,P y)
{
    int k=x.size();
    if(k==1&&x.back().X==y.X) return;
    if(k<=1) return x.push_back(y);
    while(k>1&&cr(y,x[k-1],x[k-2])<=0) x.pop_back(),k--;
    x.push_back(y);
}
inline bool cmp(P x,P y){return x.X==y.X?x.Y>y.Y:x.X<y.X;}
inline vp operator+(vp a,vp b)
{
    vp c;int i=0,j=0,n=a.size(),m=b.size();
    while(i<n&&j<m) ins(c,cmp(a[i],b[j])?a[i++]:b[j++]);
    while(i<n) ins(c,a[i++]);
    while(j<m) ins(c,b[j++]);
    return c;
}

闵可夫斯基和一样归并做到线性，于是这部分复杂度也是 \mathcal{O}(n\log n)。

总复杂度 \mathcal{O}((n+q)\log n)，代码比较好写。

我用 vector 维护凸包，尽管卡过常了，常数还是略大。

最慢点 1.12s，其实也还好。

// 洛谷 P13523
// https://www.luogu.com.cn/problem/P13523
#include<bits/stdc++.h>
#define LL long long
#define bll __int128
#define P pair<LL,LL>
#define X first
#define Y second
#define vp vector<P>
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=1e6+5;
int n,m;LL a[N];
inline P operator+(P x,P y){return {x.X+y.X,x.Y+y.Y};}
inline P operator-(P x,P y){return {x.X-y.X,x.Y-y.Y};}
inline bll operator*(P x,P y){return (bll)x.X*y.Y-(bll)x.Y*y.X;}
inline bll cr(P A,P B,P C){return (B-A)*(C-A);}
inline void ins(vp &x,P y)
{
    int k=x.size();
    if(k==1&&x.back().X==y.X) return;
    if(k<=1) return x.push_back(y);
    while(k>1&&cr(y,x[k-1],x[k-2])<=0) x.pop_back(),k--;
    x.push_back(y);
}
上凸包合并部分
inline vp mik(vp a,vp b)
{
    int n=a.size(),m=b.size();vp A(n-1),B(m-1),c;
    if(!n) return b;if(!m) return a;
    for(int i=1;i<n;i++) A[i-1]=a[i]-a[i-1];
    for(int i=1;i<m;i++) B[i-1]=b[i]-b[i-1];
    int i=0,j=0;c={a[0]+b[0]};n--,m--;
    while(i<n&&j<m) ins(c,c.back()+((A[i]*B[j]<0)?A[i++]:B[j++]));
    while(i<n) ins(c,c.back()+A[i++]);
    while(j<m) ins(c,c.back()+B[j++]);
    return c;
}
tuple<vp,vp,vp> sol(int l,int r)
{
    if(l==r) return {vp{{l,a[l]}},vp{{-l,-a[l]}},{}};
    if(l+1==r)
        return {vp{{l,a[l]},{r,a[r]}},vp{{-r,-a[r]},{-l,-a[l]}},vp{{1,a[r]-a[l]}}};
    int M=(l+r)>>1;
    auto [A,B,C]=sol(l,M);auto [D,E,F]=sol(M+1,r);
    return {A+D,B+E,C+F+mik(B,D)};
}
inline LL f(P t,LL x){return t.X*x+t.Y;}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
    vp g=get<2>(sol(0,n));
    for(int x;m--;)
    {
        cin>>x;int l=1,r=g.size()-1,M,s=0;
        while(l<=r) M=(l+r)>>1,f(g[M],x)>f(g[M-1],x)?s=M,l=M+1:r=M-1;
        cout<<f(g[s],x)<<"\n";
    }
    return 0;
}