P7294 [USACO21JAN] Minimum Cost Paths P 题解

· · 题解

给一种比较无脑的解法。

首先交换题目中 x,y 的顺序，然后设 f_{i,j} 表示走到 (i,j) 这个点的最小代价。

转移有：

f_{i,j} = \min(f_{i-1,j}+j^2,f_{i,j-1}+c_i)

考虑经典套路，对 f_{i,*} 作差分得到 g_{i,j}=f_{i,j}-f_{i,j-1}，即有等式 \sum_{j=1}^k g_{i,j}=f_{i,k}。

注意到 f_{*,1} 和 g_{*,1} 是常量，所以以下讨论中均不考虑这两项。

考虑一行一行地转移，首先 f_{i,j} 继承 f_{i-1,j}+j^2，此时，g_{i,j}=g_{i-1,j}+2j-1。

然后对所有 j 依次执行 f_{i,j} = \min(f_{i,j},f_{i,j-1}+c_i)，对应到 g 上的操作就是如果 g_{i,j} \ge c_i，设 x = g_{i,j}-c_i，那么 g_{i,j} \gets g_{i,j}-x，g_{i,j+1} \gets g_{i,j+1}+x。

观察此过程，我们发现，g_{i,j} 随着 j 的增长而递增，证明可以使用归纳法，因此，我们有了下面的文字描述：

首先令 g_{i,j}=g_{i-1,j}+2j-1。

然后找到第一个大于等于 c_i 的 g_{i,j}，令 g_{i,j} \gets c_i（\Delta \gets g_{i,j}-c_i），然后 g_{i,j+1} \gets \Delta+g_{i,j+1}，以此类推。

最后 g 的形态是前面若干个小于等于 c_i 的值，后面全部变成 c_i。

于是，我们再次对 g 做一次差分得到 h 数组，那么对于 h 来说，操作变成了：

首先令 h_{i,j}=h_{i-1,j}+2。

然后找到第一个 j 满足 \sum_{k=1}^j h_{i,k} \ge c_i，令 h_{i,j} = c_i-\sum_{k=1}^{j-1} h_{i,k}，剩下的 h_{i,p} \gets 0(p>j)。

第一步可以使用区间加操作，第二步可以线段树上二分，最后一步是单点修改。

为了方便起见，线段树的每个节点可以维护两个值 c0,c1 表示这里一共有 c0 个值为 c1 的 h，这样的话我们就可以不用动态开点了，常数也特别小。

最后查询离线下来，对 h 求一个二阶前缀和就可以了。

时间复杂度 O(n \log n)，空间复杂度 O(n)。

#include<bits/stdc++.h>
#define ll long long
#define N 200005
using namespace std;
struct noede{ll x,y,id;}p[N];
bool cmp(noede a,noede b){return a.x<b.x;}
struct node{ll sum,sum1,cnt,tag;}tr[N<<2];
ll n,m,q,i,j,a[N],ans[N],root,top,f1;
inline void pushup(ll p,ll s,ll t){
    tr[p].cnt = tr[2*p].cnt+tr[2*p+1].cnt;
    tr[p].sum = tr[2*p].sum+tr[2*p+1].sum;
    tr[p].sum1 = tr[2*p+1].sum1+tr[2*p].sum1+tr[2*p].sum*tr[2*p+1].cnt;
}
inline void pushtag(ll p,ll c){tr[p].tag+=c,tr[p].sum+=tr[p].cnt*c,tr[p].sum1+=(1+tr[p].cnt)*tr[p].cnt/2*c;}
inline void pushdown(ll p){pushtag(2*p,tr[p].tag),pushtag(2*p+1,tr[p].tag),tr[p].tag=0;}
inline void add(ll x,ll c1,ll c2,ll s,ll t,ll p){
    if(s==t){
        tr[p].cnt=c1,tr[p].sum=c1*c2,tr[p].sum1=(1+c1)*c1/2*c2;
        return ;
    }
    if(tr[p].tag) pushdown(p);
    if(x<=(s+t)/2) add(x,c1,c2,s,(s+t)/2,2*p);
    else add(x,c1,c2,(s+t)/2+1,t,2*p+1);
    pushup(p,s,t);
}
inline pair<ll,ll> query(ll cnt,ll s,ll t,ll p){
    if(!cnt) return make_pair(0,0);
    if(s==t) return make_pair(cnt*(tr[p].sum/tr[p].cnt),(1+cnt)*cnt/2*(tr[p].sum/tr[p].cnt));
    if(tr[p].tag) pushdown(p);
    if(tr[2*p].cnt<cnt){
        pair<ll,ll> ans = query(cnt-tr[2*p].cnt,(s+t)/2+1,t,2*p+1); 
        ans.first += tr[2*p].sum,ans.second += tr[2*p].sum*(cnt-tr[2*p].cnt)+tr[2*p].sum1;
        return ans;
    }
    else return query(cnt,s,(s+t)/2,2*p);
}
inline pair<ll,ll> querys(ll x,ll s,ll t,ll p){
    if(s==t) return make_pair(tr[p].cnt,tr[p].sum/tr[p].cnt);
    if(tr[p].tag) pushdown(p);
    if(x<=(s+t)/2) return querys(x,s,(s+t)/2,2*p);
    else return querys(x,(s+t)/2+1,t,2*p+1);
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(i=1;i<=m;i++) scanf("%lld",&a[i]);
    scanf("%lld",&q);
    for(i=1;i<=q;i++) scanf("%lld%lld",&p[i].x,&p[i].y),swap(p[i].x,p[i].y),p[i].id=i;
    sort(p+1,p+q+1,cmp);
    top=1,add(1,1,a[1],1,2e5,1);
    for(i=1,j=1;i<=m;i++){
        top++,add(top,1e9,0,1,2e5,1);
        for(;j<=q&&p[j].x==i;j++) ans[p[j].id]=f1*p[j].y+query(p[j].y-1,1,2e5,1).second;
        if(i!=m){
            f1++,pushtag(1,2);
            if(f1+querys(1,1,2e5,1).second>=a[i+1]){
                while(top) add(top,0,0,1,2e5,1),top--;
                top=1,add(1,1,a[i+1]-f1,1,2e5,1);
            }
            else{
                pair<ll,ll> las;
                while(f1+tr[1].sum>=a[i+1]&&top>=1){
                    las = querys(top,1,2e5,1),add(top,0,0,1,2e5,1);
                    top--;
                }
                ll delta = (a[i+1]-tr[1].sum-f1),num = (las.second==0?0:delta/las.second),rest = delta-num*las.second;
                if(num) top++,add(top,num,las.second,1,2e5,1);
                if(rest) top++,add(top,1,rest,1,2e5,1);
            }
        }
    }
    for(i=1;i<=q;i++) printf("%lld\n",ans[i]);
    return 0;
}