题解 CF1334F 【Strange Function】

Alex_Wei · 2020-04-11 13:37:12 · 题解

LG 传送门 & CF 传送门。

题意简述：

定义序列函数 f(x)：所有满足 x_i>x_{1\cdots i-1} 的 x_i 组成的序列。如 f[3,1,2,7,7,3,6,7,8]=[3,7,8]。

给出三个序列 a,p,b，删除 a_i 的代价为 p_i（p_i 可能为负）。求使 f(a)=b 的最小代价。无解输出 \texttt{NO}。

显然如果 b 不是 a 的子序列肯定无解，否则一定有解。

按照 a_i 从小到大 DP，设 f_i 为以 i 结尾的最小代价：

如果 a_i\notin b，则忽略。
如果 a_i\in b，设 a_i=b_j，则 f_i=\min_{x=1}^{i-1}(f_x+\operatorname{contri}(x+1,i-1,b_{j-1}))[a_x=b_{j-1}]。其中 \operatorname{contri}(l,r,v) 为区间 [l,r] 需要被删除的数之和，即 i\in[l,r] 中所有满足 a_i\geq v 或 q_i<0 的 q_i 之和，可以用主席树求出。

主席树常数大又难写？考虑到 \operatorname{contri}(l,r,b_{j-1}) 和 \operatorname{contri}(l,r,b_j) 之间只改变了所有满足 b_{j-1}<a_x\leq b_j 的 q_x 的贡献，用树状数组维护即可。

可以看出这样 DP 是 O(n^2\log n) 的。其实并不需要枚举所有 x，求 f_i 时：

如果这是 b_j 第一次在 a 出现，直接按照上面的方程 DP 即可。
否则设 b_j 前一次出现在 a_y（即 y<i，a_y=b_j），则一开始直接计算 f_i=f_y+\operatorname{contri}(y,i-1) 就可以替代所有小于 y 且 a_x=b_{j-1} 的转移。
这样每个数只会被转移 1 次，单次时间复杂度 O(\log n)（计算 \operatorname{contri} 的 \log）。

需要注意边界条件，可以适当设置边界值方便写代码。

判断是否有解 O(n\log n)，DP 过程 O(n\log n)，总时间复杂度 O(n\log n)。在 CF 上跑的飞快。

const int N=5e5+5;

vector <int> buc[N];
ll n,m,a[N],b[N],p[N],f[N],c[N];
void modify(int x,int v){while(x<=n)c[x]+=v,x+=x&-x;}
ll query(int x){ll ans=0; while(x)ans+=c[x],x-=x&-x; return ans;}
ll cal(int l,int r){return query(r)-query(l-1);}

int main(){
    n=read()+1,mem(f,0x3f),f[0]=0;
    for(int i=1;i<n;i++)a[i]=read(),buc[a[i]].pb(i);
    buc[0].pb(0),buc[n].pb(n);
    for(int i=1;i<n;i++)p[i]=read(),modify(i,p[i]);
    b[m=read()+1]=n; for(int i=1;i<m;i++)b[i]=read();

    for(int i=1;i<=m;i++){
        if(i>1)for(int j=b[i-2]+1;j<=b[i-1];j++)
            for(int k:buc[j])if(p[k]>0)modify(k,-p[k]);
        int pos=-1,sz=buc[b[i-1]].size()-1;
        for(int j=0;j<buc[b[i]].size();j++){
            int k=buc[b[i]][j];
            if(j)f[k]=f[buc[b[i]][j-1]]+cal(buc[b[i]][j-1],k-1);
            while(pos<sz&&buc[b[i-1]][pos+1]<k){
                int l=buc[b[i-1]][++pos];
                f[k]=min(f[k],f[l]+cal(l+1,k-1));
            }
        }
    }
    if(f[n]<1e16)printf("YES\n%lld\n",f[n]);
    else puts("NO");

    return 0;
}

应该有更简单的方法，到时候再来填坑。

Upd on 2020.4.15：把代码改整洁了。

不填坑了，丢个完整代码自己体会（

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N=5e5+5;
int n,m,a[N],b[N],p[N],ind[N];
ll c[N];
void modify(int x,ll v){x++; while(x<=m+1)c[x]+=v,x+=x&-x;}
ll query(int x){x++; ll ans=0; while(x)ans+=c[x],x-=x&-x; return ans;}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    for(int i=1;i<=n;i++)scanf("%d",p+i);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)scanf("%d",b+i),ind[b[i]]=i;
    modify(1,1e18);
    for(int i=1;i<=n;i++){
        ll v,nv;
        if(ind[a[i]])v=query(ind[a[i]]-1);
        modify(0,p[i]);
        if(p[i]>0)modify(lower_bound(b+1,b+m+1,a[i])-b,-p[i]);
        if(ind[a[i]]){
            nv=query(ind[a[i]]);
            if(v<nv)modify(ind[a[i]],v-nv),modify(ind[a[i]]+1,nv-v);
        }
    }
    ll ans=query(m);
    if(ans>1e16)puts("NO");
    else printf("YES\n%lld\n",ans);

    return 0;
}