题解归档 - cf455E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf455E
• 本地来源：problems/cf455E/idea.md
• 题目链接：https://codeforces.com/contest/455/problem/E
• 原始标题：CF455E Function

思路

CF455E Function

题意

给定数组 a[1..n]，定义：

• f(1,j) = a[j]
• f(i,j) = min(f(i-1,j), f(i-1,j-1)) + a[j]（2≤i≤j）

共 m 次询问 (x,y)，求 f(x,y)。

转化

从 (x,y) 出发做 x 步，每步可「原地不动」或「左移一格」，站在位置 p 代价 a[p]，求最小总代价。

对固定右端点 y、左端点 l∈[y-x+1,y]：最优策略是让区间 [l,y] 内最小值 a[l] 被访问 (x-(y-l)) 次，其余各访问 1 次。利用前缀和 sum：

[
\text{cost}(l) = sum[y] - sum[l] + a[l]\cdot(x-(y-l))
= sum[y] + a[l]\cdot(x-y) + (a[l]\cdot l - sum[l])
]

令 K=a[l]，B=a[l]*l-sum[l]，X=x-y，则

[
f(x,y) = sum[y] + \min_{l\in[y-x+1,y]} (K\cdot X + B)
]

即区间 [y-x+1,y] 上多条直线在 X=x-y（非正）处取下包络最小值。

算法

• 预处理 sum
• 第 i 条直线：斜率 a[i]，截距 a[i]*i-sum[i]
• 线段树每个节点维护该区间内直线的下凸包
• 询问：区间 [y-x+1,y]，查询 x=y-x，答案 sum[y]+query

复杂度：O(n log n) 建树，O(log^2 n) 每次询问。

验证

• 样例通过
• WSL 对拍 500 组（n≤45）与 O(n^2) DP 暴力一致
• Kali 远端当前不可达，未走 stress.py 官方通道

结论

线段树套下凸包（CHT），Div.1 E 经典题。

代码

来源：problems/cf455E/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:38:13
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100005;
const ll inf=4e18;
ll a[maxn+5],s[maxn+5],n,i,j,k,zc,pd,cur,dq,cnt,ans;
struct tnode{
    vector<pair<ll,ll>>hull;
    ll qry(ll x){
        if(hull.empty()) return inf;
        ll l=0,r=(ll)hull.size()-1;
        while(l<r){
            ll mid=(l+r)>>1;
            if(hull[mid].first*x+hull[mid].second<=hull[mid+1].first*x+hull[mid+1].second) r=mid;
            else l=mid+1;
        }
        return hull[l].first*x+hull[l].second;
    }
};
tnode t[maxn*4+5];
vector<pair<ll,ll>>buf[maxn*4+5];
bool bad(ll m1,ll b1,ll m2,ll b2,ll m3,ll b3){
    return (__int128)(b3-b1)*(m1-m2)>=(__int128)(b2-b1)*(m1-m3);
}
void mkhull(ll rt){
    ll m,b,ss;
    sort(buf[rt].begin(),buf[rt].end());
    t[rt].hull.clear();
    for(ss=0;ss<(ll)buf[rt].size();ss++){
        m=buf[rt][ss].first;
        b=buf[rt][ss].second;
        if(!t[rt].hull.empty() and t[rt].hull.back().first==m){
            if(b<t[rt].hull.back().second) t[rt].hull.back().second=b;
            continue;
        }
        while((ll)t[rt].hull.size()>=2){
            pd=(ll)t[rt].hull.size();
            if(bad(t[rt].hull[pd-2].first,t[rt].hull[pd-2].second,t[rt].hull[pd-1].first,t[rt].hull[pd-1].second,m,b)) t[rt].hull.pop_back();
            else break;
        }
        t[rt].hull.push_back({m,b});
    }
}
void build(ll rt,ll l,ll r){
    if(l==r){
        buf[rt].push_back({a[l],a[l]*l-s[l]});
        mkhull(rt);
        return;
    }
    ll mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    buf[rt]=buf[rt<<1];
    for(i=0;i<(ll)buf[rt<<1|1].size();i++) buf[rt].push_back(buf[rt<<1|1][i]);
    mkhull(rt);
}
ll qry(ll rt,ll l,ll r,ll ql,ll qr,ll x){
    if(ql>r or qr<l) return inf;
    if(ql<=l and r<=qr) return t[rt].qry(x);
    ll mid=(l+r)>>1;
    return min(qry(rt<<1,l,mid,ql,qr,x),qry(rt<<1|1,mid+1,r,ql,qr,x));
}
int main(){
    ll m,x,y;
    cin>>n;
    s[0]=0;
    for(i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    build(1,1,n);
    cin>>m;
    while(m--){
        cin>>x>>y;
        cur=s[y]+qry(1,1,n,y-x+1,y,x-y);
        cout<<cur<<"\n";
    }
    return 0;
}