题解：P8239 [AGM 2022 资格赛] 分裂

· · 题解

题意

给定一个长度为 n 的正整数数组 a_1, a_2, \dots, a_n 和一个长度为 K 的正整数数组 b_1, b_2, \dots, b_K。 需要将数组 a 划分为 K 个非空连续子段，设第 j 段的最大值和最小值分别为 mx_j 和 mn_j，求最大总得分：

\sum_{j=1}^K \left(mx_j^{b_j} - mn_j^{b_j}\right)

数据范围：1 \le K \le n \le 5000，1 \le a_i \le 10^5，1 \le b_i \le 3。

思路

应该没有比我还抽象的做法了吧？

我们先考虑 O(n^2K) 的暴力DP。

定义 dp_{i,j} 表示前 i 个位置分为 j 段的最大得分，有

dp_{i, j} = \max_{j-1 \le k < i} \left\{ dp_{k, j-1} + \left(\max_{k < p \le i} a_p\right)^{b_j} - \left(\min_{k < p \le i} a_p\right)^{b_j} \right\}

这个是容易的。

考虑线段树优化，大概就是固定第二维，然后枚举第一维。

我们的线段树维护的是从第 p 个位置转移过来的值，其中包括了 p 本来的 DP 值加上区间最大值再减去区间最小值，也就是 d_p+mx_p-mn_p=val_p（这里的 mx_p, mn_p 指对应极值的 b_j 次方）。

此时，每新加入一个元素，都会同时更新一个后缀的 mx 和 mn，也就是后缀覆盖的操作。

但是我们发现这样是 O(nK\log n) 的，这无疑是过不了的。骗你的，这东西优化到 O(nK) 也要卡常。

我们注意到做完区间覆盖操作之后，这个区间内的 val 的相对大小就不会改变了。因为之后都是一起被覆盖。

所以此时我们就可以把这个区间合并为一个段。

如果说这个题只有一个极值的话，那这道题就做完了。\ 但是这道题有两个极值，两个值会互相干扰。

于是我们取分割点的并集，也就是一个段内的 mx 和 mn 都相同，段内只需要保留最大的 d_p。

但是，如果两个段之间的缝隙，它的左右 mx 和 mn 都不同（即同时存在 \max 和 \min 两条缝），那覆盖一次是不够的，要覆盖两次把两条缝都消掉，左右两个段才能真正合并成一个段。而只覆盖第一次的时候，我们虽然不能直接合并段，但这些被覆盖的段拥有了相同的 mx（或 mn），我们要能 O(1) 更新它们的整体信息。

为此，我们在“段”之上再维护两种块，一个叫 MAX 块，一个叫 MIN 块：

在每个块内部，我们除了用双向链表串起所有段，还额外维护一个按 dp - mn（MIN 块则是 dp + mx）单增的单调队列：因为弹栈永远从块的最右侧开始弹，如果左边的段权值比右边大，那右边的段既活得没左边久、权值又没左边大，就永远不可能成为最优，可以直接从单调队列里删掉。这样队尾就永远是块内权值最大的段，修改整个块的 mx（或 mn）时就能 O(1) 更新块的最大得分。

于是，当我们用新加入的 v 向左覆盖最大值时（最小值同理）：

  1. 如果栈顶是 MAX 块，且块的 mx \le v：直接把整个块的 mx 改成 v，然后把两个 MAX 块的链表和单调队列合并（如果两块交界处的两个段连 mn 也相同，说明交界处的两条缝都消掉了，就把这两个段真正合并成一个段）。
  2. 如果栈顶是 MIN 块，且其最右段的 mx \le v：由于 MIN 块内部的段本来就已经有相同的 mn（只剩一条 \max 缝），现在连 mx 也被 v 覆盖了，说明这些段的两条缝都已经消光了。此时直接从 MIN 块右侧把所有 mx \le v 的段依次弹出（同步在链表和单调队列中删除），取它们最大的 dp ，合并成一个新段，再并入当前的 MAX 块即可。

这样是可以均摊掉的：每个位置初始只会产生 \max 和 \min 两条缝隙，所以总共 2n 条缝隙，每消掉一个缝隙都是均摊 O(1) 的，所以每一层都是 O(n) 的，总时间复杂度 O(nK)。

代码

#include<bits/stdc++.h>
#define double long double
#define int long long
using namespace std;
const double eps=1e-6;
const int inf=0x3f3f3f3f3f3f3f3f,N=5010,mod=1e9+7;
struct Node
{
    int dp,mx,mn,lq,rq,lidx,ridx;
    bool flag;
}seg[3*N];
struct Block
{
    int type,mx,idx1,idx2,q1,q2,sum,ss;
};
int a[N],b[N],dp[2][N];
vector<Block> st;
int n,k,cnt;
int power(int a,int b,int p)
{
    int res=1;
    while (b)
    {
        if (b&1)
        {
            res=res*a%p;
        }
        a=a*a%p;
        b>>=1;
    }
    return res;
}
int get(int idx,int type)
{
    return type==0?seg[idx].dp-seg[idx].mn:seg[idx].dp+seg[idx].mx;
}
void update(Block& x)
{
    x.sum=x.type==0?get(x.q2,x.type)+x.mx:get(x.q2,x.type)-x.mx;
    return;
}
int new_node(int dp,int mx,int mn)
{
    int idx=++cnt;
    seg[idx]={dp,mx,mn,0,0,0,0,true};
    return idx;
}
Block pack(int type,int mx,int idx)
{
    seg[idx].lq=seg[idx].rq=0;
    seg[idx].lidx=seg[idx].ridx=0;
    seg[idx].flag=true;
    Block temp={type,mx,idx,idx,idx,idx,0,0};
    update(temp);
    return temp;
}
void push(Block blk)
{
    update(blk);
    blk.ss=blk.sum;
    if (!st.empty())
    {
        blk.ss=max(blk.ss,st.back().ss);
    }
    st.push_back(blk);
    return;
};
int pop(Block& blk)
{
    int idx=blk.idx2,p=seg[idx].lq;
    if (p)
    {
        seg[p].rq=0;
    }
    else
    {
        blk.idx1=0;
    }
    blk.idx2=p;
    seg[idx].lq=seg[idx].rq=0;
    if (seg[idx].flag)
    {
        int cur=seg[idx].lidx;
        if (cur)
        {
            seg[cur].ridx=0;
        }
        else
        {
            blk.q1=0;
        }
        blk.q2=cur;
        seg[idx].lidx=seg[idx].ridx=0;
        seg[idx].flag=false;
    }
    if (blk.idx1)
    {
        update(blk);
    }
    return idx;
}
Block merge(Block t1,Block t2)
{
    if (!t1.idx1)
    {
        return t2;
    }
    if (!t2.idx1)
    {
        return t1;
    }
    int l=t1.idx2,r=t2.idx1;
    if (t1.type==0&&seg[l].mn==seg[r].mn||t1.type==1&&seg[l].mx==seg[r].mx)
    {
        pop(t1);
        seg[r].dp=max(seg[r].dp,seg[l].dp);
        int nk=get(r,t2.type),cur=seg[r].ridx;
        while (cur&&get(cur,t2.type)<=nk)
        {
            int nxt=seg[cur].ridx;
            seg[cur].flag=false;
            seg[cur].lidx=seg[cur].ridx=0;
            cur=nxt;
        }
        seg[r].ridx=cur;
        if (cur)
        {
            seg[cur].lidx=r;
        }
        else
        {
            t2.q2=r;
        }
        update(t2);
        if (!t1.idx1)
        {
            return t2;
        }
    }
    seg[t1.idx2].rq=t2.idx1;
    seg[t2.idx1].lq=t1.idx2;
    t1.idx2=t2.idx2;
    int cur=t2.q1;
    while (cur&&get(cur,t2.type)<=get(t1.q2,t1.type))
    {
        int nxt=seg[cur].ridx;
        seg[cur].flag=false;
        seg[cur].lidx=seg[cur].ridx=0;
        cur=nxt;
    }
    if (cur)
    {
        seg[t1.q2].ridx=cur;
        seg[cur].lidx=t1.q2;
        t1.q2=t2.q2;
    }
    update(t1);
    return t1;
}
void solve()
{
    cin>>n>>k;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for (int i=1;i<=k;i++)
    {
        cin>>b[i];
    }
    fill(dp[0],dp[0]+n+1,-inf);
    dp[0][0]=0;
    for (int i=1;i<=k;i++)
    {
        st.clear();
        fill(dp[i&1],dp[i&1]+n+1,-inf);
        cnt=0;
        for (int j=1;j<=n;j++)
        {
            int v=power(a[j],b[i],inf),temp=new_node(dp[i&1^1][j-1],v,v);
            bool flag1=false,flag2=false;
            if (!st.empty())
            {
                Block& c=st.back();
                int last_mx=(c.type==0)?c.mx:seg[c.idx2].mx;
                int last_mn=(c.type==1)?c.mx:seg[c.idx2].mn;
                if (last_mx<=v)
                {
                    flag1=true;
                }
                if (last_mn>=v)
                {
                    flag2=true;
                }
            }
            if (flag1)
            {
                Block cur=pack(0,v,temp);
                while (!st.empty())
                {
                    Block& c=st.back();
                    if (c.type==0)
                    {
                        if (c.mx<=v)
                        {
                            Block blk=c;
                            st.pop_back();
                            blk.mx=v;
                            update(blk);
                            cur=merge(blk,cur);
                        }
                        else
                        {
                            break;
                        }
                    }
                    else
                    {
                        if (seg[c.idx2].mx<=v)
                        {
                            int maxx=-inf,mn=c.mx;
                            while (c.idx1&&seg[c.idx2].mx<=v)
                            {
                                maxx=max(maxx,seg[pop(c)].dp);
                            }
                            if (!c.idx1)
                            {
                                st.pop_back();
                            }
                            else
                            {
                                update(c);
                                c.ss=c.sum;
                                if (st.size()>=2)
                                {
                                    c.ss=max(c.ss,st[st.size()-2].ss);
                                }
                            }
                            int temp=new_node(maxx,v,mn);
                            cur=merge(pack(0,v,temp),cur);
                        }
                        else
                        {
                            break;
                        }
                    }
                }
                push(cur);
            }
            else if (flag2)
            {
                Block cur=pack(1,v,temp);
                while (!st.empty())
                {
                    Block& c=st.back();
                    if (c.type==1)
                    {
                        if (c.mx>=v)
                        {
                            Block blk=c;
                            st.pop_back();
                            blk.mx=v;
                            update(blk);
                            cur=merge(blk,cur);
                        }
                        else
                        {
                            break;
                        }
                    }
                    else
                    {
                        if (seg[c.idx2].mn>=v)
                        {
                            int maxx=-inf,mx=c.mx;
                            while (c.idx1&&seg[c.idx2].mn>=v)
                            {
                                maxx=max(maxx,seg[pop(c)].dp);
                            }
                            if (!c.idx1)
                            {
                                st.pop_back();
                            }
                            else
                            {
                                update(c);
                                c.ss=c.sum;
                                if (st.size()>=2)
                                {
                                    c.ss=max(c.ss,st[st.size()-2].ss);
                                }
                            }
                            int temp=new_node(maxx,mx,v);
                            cur=merge(pack(1,v,temp),cur);
                        }
                        else
                        {
                            break;
                        }
                    }
                }
                push(cur);
            }
            else
            {
                push(pack(0,v,temp));
            }
            if (j>=i)
            {
                dp[i&1][j]=st.back().ss;
            }
        }
    }
    cout<<dp[k&1][n]<<'\n';
}
signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int TestCase=1;
    // cin>>TestCase;
    for (int Caseid=1;Caseid<=TestCase;Caseid++)
    {
        solve();
    }
    return 0;
}

这个是没有卡常的，有82分。

卡常之后的代码在这里。