题解 P9499 「RiOI-2」change

· · 题解

写一个 dp 做法。

首先有一个很暴力的 dp，设 dp_{i,j} 表示算完前 i 个，从 i 移到 i+1 的个数大于等于 j 个然后转移即可。

尝试直接维护这个 dp，首先我们把 x_i=1 的段合并在一起，也就是说如果能通过 x_i=1 一直往后移到比当前位置大的位置，那么就移。发现这样子之后 c_i 不为 0 的位置一定在段内的 v_i 的后缀最大值处。

接下来考虑 dp 的时候我们在干什么，设 cost_{i,k} 为第 i 段的这些 c_i 选 k 个要往后移的最大贡献，val_i 为第 i 段的 v 的最大值。那么转移是先枚举从 i-1 段移过来个数 j，然后枚举这一段要往后移的个数 k，有 dp_{i,\lfloor\frac{j+k}{x_i}\rfloor}=\max(dp_{i,\lfloor\frac{j+k}{x_i}\rfloor},dp_{i-1,j}+cost_{i,k})，然后 dp_{i,j}=\max(dp_{i,j},dp_{i,j+1}+v_{i+1})。

首先可以发现 cost_{i} 是一个上凸壳，所以每次的转移的第一步是一个闵可夫斯基和，可以在两个凸壳大小的和时间内完成。

接下来要做的是将坐标除以这一段最右点的 x_i，这个也可以在凸壳大小内完成。然后还有一步是 dp_{i,j}=\max(dp_{i,j},dp_{i,j+1}+v_{i+1})，这一步相当于 pop 掉凸壳前面一部分斜率大于 v_{i+1} 的点，直接 pop 就行。

考虑这个做法的复杂度，除以 x_i 的时候凸包上每个点的横坐标至少除以二。所以凸包大小总和大概是 n\log v 级别，时间复杂度即为 O(n\log v)。

// Problem: T351677 「RiOI-2」change
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/T351677?contestId=122187
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll __int128
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) (int)((x).size())
#define int ll
#define N 200005
using namespace std;
inline char gc(){static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
#define gc getchar
inline ll read(){char c=gc();ll su=0,f=1;for (;c<'0'||c>'9';c=gc()) if (c=='-') f=-1;for (;c>='0'&&c<='9';c=gc()) su=su*10+c-'0';return su*f;}
inline void write(ll x){if (x<0){putchar('-');write(-x);return;}if (x>=10) write(x/10);putchar(x%10+'0');}
inline void writesp(ll x){write(x),putchar(' ');}
inline void writeln(ll x){write(x);putchar('\n');}
int n,a[N],b[N],x[N],suf[N];
bitset<10000005>vis;
struct node
{
    vector<int>x,y;
    node()
    {
        poly().swap(x),poly().swap(y);
    }
    void ins(int a,int b)
    {
        while (x.size()>0&&a==x.back()&&b>=y.back()) x.pop_back(),y.pop_back();
        if (x.size()>0&&a==x.back()&&b<y.back()) return;
        x.push_back(a);
        y.push_back(b);
    }
    void add(int k)
    {
        int l=0;
        int mx=0;
        for (int i=1;i<x.size();i++)
        {
            mx=max(mx,y[i]+x[i]*k);
            if ((y[i]-y[i-1])/(x[i]-x[i-1])>=-k) 
            {
                l=i;
            }
        }
        if (l==0) return;
        poly xx,yy;
        xx.push_back(0);yy.push_back(mx);
        for (int i=l;i<x.size();i++)
            xx.push_back(x[i]),yy.push_back(y[i]);
        x.swap(xx);
        y.swap(yy);
    }
    void selfclr()
    {
        for (int i=0;i<x.size();i++) vis[i]=0;
        int t=0;
        for (int i=1;i+1<x.size();i++)
        {
            if ((y[i]-y[i-1])*(x[i+1]-x[i])==(y[i+1]-y[i])*(x[i]-x[i-1]))
                vis[i]=1,t=1;
        }
        if (!t) return;
        poly xx,yy;
        for (int i=0;i<x.size();i++)
            if (!vis[i])
                xx.push_back(x[i]),yy.push_back(y[i]);
        x.swap(xx);
        y.swap(yy);
    }
};
pa all[10000005];
int cnt;
node merge(node x,node y)
{
    cnt=0;
    for (int i=1;i<x.x.size();i++)
    {
        all[++cnt]=mp(x.x[i]-x.x[i-1],x.y[i]-x.y[i-1]);
    }
    for (int i=1;i<y.x.size();i++)
    {
        all[++cnt]=mp(y.x[i]-y.x[i-1],y.y[i]-y.y[i-1]);
    }
    node res;
    res.ins(0,x.y[0]+y.y[0]);
    sort(all+1,all+cnt+1,[&](pa x,pa y)
    {
        return x.se*y.fi>y.se*x.fi;
    });
    for (int i=1;i<=cnt;i++)
        res.ins(res.x.back()+all[i].fi,res.y.back()+all[i].se);
    return res;
}
void outp(node x)
{
    for (int i=0;i<x.x.size();i++)
        writesp(x.x[i]),writeln(x.y[i]);
    puts("");
}
void BellaKira()
{
    n=read();
    for (int i=1;i<=n;i++) a[i]=read();
    for (int i=1;i<=n;i++) b[i]=read();
    node dp;
    dp.x.push_back(0);
    dp.y.push_back(0);
    node st=dp;
    for (int i=1;i<n;i++) x[i]=read();
    x[n]=1;
    suf[n+1]=-1;
    for (int i=n;i>=1;i--)
    {
        suf[i]=a[i];
        if (x[i]==1) suf[i]=max(suf[i],suf[i+1]);
    }
    for (int i=1;i<n;i++)
    {
        if (x[i]==1&&suf[i+1]>=suf[i]) b[i+1]+=b[i],b[i]=0;
    }
    for (int l=1;l<=n;l++)
    {
        int r=l;
        while (r<n&&x[r]==1) r++;
        node nw=st;
        int sum=0;
        for (int i=r;i>=l;i--) sum+=a[i]*b[i];
        nw.y[0]=sum;
        for (int i=r;i>=l;i--)
            if (b[i])
            {
                nw.ins(nw.x.back()+b[i],sum-a[i]*b[i]);
                sum-=a[i]*b[i];
            }
        dp.add(suf[l]);
        nw=merge(dp,nw);
        if (r==n) 
        {
            dp=nw;
            break;
        }
        dp=node();
        dp.ins(0,nw.y[0]);
        for (int i=1;i<nw.x.size();i++)
        {
            {
                if (nw.x[i]/x[r]!=nw.x[i-1]/x[r])
                {
                    dp.ins(nw.x[i]/x[r],nw.y[i]-(nw.y[i]-nw.y[i-1])*(nw.x[i]%x[r])/(nw.x[i]-nw.x[i-1]));
                }
            }
            dp.ins(nw.x[i]/x[r],nw.y[i]);
            if (i+1<nw.x.size())
            {
                if (nw.x[i+1]/x[r]!=nw.x[i]/x[r])
                {
                    dp.ins(nw.x[i]/x[r]+1,nw.y[i]+(x[r]-nw.x[i]%x[r])*(nw.y[i+1]-nw.y[i])/(nw.x[i+1]-nw.x[i]));
                }
            }
        }
        dp.selfclr();
        l=r;
    }
    writeln(dp.y[0]%mod);

}
signed main()
{
    int id=read();
    int T=read();
    while (T--)
    {
        BellaKira();
    }
}