CF2027D2 The Endspeaker (Hard Version) 题解

· · 题解

Solution

注意到 nm\le 3\times 10^5，考虑设计出一份能与 nm 扯上关系的代码。

贪心想不出来就来想 dp。设 dp_{i,j} 表示 k 的值目前为 i，a 中剩下的第一个元素下标为 j 的最小代价。枚举状态就是 O(nm) 的，感觉很有前途。从 j 开始往后找到第一个位置 c 满足 a 中 i\sim c 的和大于 b_j，有转移：dp_{i,c}\gets dp_{i,j}+m-i，因为每次转移一个极大的连续段肯定更优。还有种情况是直接使 k 往后移，即 dp_{i+1,j}\gets dp_{i,j}。初始化 dp_{1,1}=0，答案为 \displaystyle\min_{i=1}^m dp_{i,n+1}。

这样做答案是对了，但是方案会有缺漏。

问题出在每次可以不用转移极大连续段，只选取其中的一小段前缀进行转移，即对于 p\in(i,c] 都有转移 dp_{i,p}\gets dp_{i,j}+m-i。之前不这样做是因为答案不会更优却会提升复杂度，现在为了统计方案确实是有必要的。

区间更新，单点查询，直接上线段树维护转移。

时间复杂度：O(nm\log n)。

Code

极其丑陋。

#include<bits/stdc++.h>
typedef long long ll;
typedef std::pair<ll,int> pli;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
inline void operator+=(pli&x,const pli&y){
    if(x.first!=y.first){
        if(x.first>y.first)x=y;
    }else if((x.second+=y.second)>=mod)
        x.second-=mod;
}
struct segment{
    int l,r;
    pli v;
}t[1200005];
void build(int p,int l,int r){
    t[p].l=l;t[p].r=r;
    t[p].v.first=inf;t[p].v.second=0;
    if(l==r)return l==1?t[p].v.first=0,t[p].v.second=1:0,void();
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}
inline void tag_down(int p){
    if(t[p].v.first!=inf)
        t[p<<1].v+=t[p].v,t[p<<1|1].v+=t[p].v,t[p].v.first=0x3f3f3f3f3f3f3f3f,t[p].v.second=0;
}
void upd(int p,int l,int r,const pli&x){
    if(t[p].l>=l&&t[p].r<=r)return t[p].v+=x;
    tag_down(p);
    int mid=t[p].l+t[p].r>>1;
    if(l<=mid)upd(p<<1,l,r,x);
    if(r>mid)upd(p<<1|1,l,r,x);
}
pli ask(int p,int x){
    if(t[p].l==t[p].r)return t[p].v;
    tag_down(p);
    return ask(p<<1|(x>(t[p].l+t[p].r>>1)),x);
}
std::vector<ll>a;
std::vector<int>b;
int T,n,m;
std::pair<ll,int>ans;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        a.resize(n+1);
        for(int i=1;i<=n;++i)
            scanf("%lld",&a[i]),a[i]+=a[i-1];
        b.resize(m+1);
        for(int i=1;i<=m;++i)
            scanf("%d",&b[i]);
        build(1,1,n);
        ans.first=inf;ans.second=0;
        for(int j=1;j<=m;++j){
            static pli res,val;
            res.first=inf;res.second=0;
            for(int i=1,k;i<=n;++i){
                k=std::upper_bound(a.begin()+i,a.begin()+n+1,b[j]+(i?a[i-1]:0))-a.begin();
                if(i<k){
                    val=ask(1,i);val.first+=m-j;
                    if(k==n+1)res+=val,--k;
                    if(i<k)upd(1,i+1,k,val);
                }
            }
            ans+=res;
        }
        if(ans.first==0x3f3f3f3f3f3f3f3f)puts("-1");
        else printf("%lld %d\n",ans.first,ans.second);
    }
    return 0;
}

好笑的是 D2 跑得比 D1 快。