题解：P11727 [JOIG 2025] 神経衰弱 2 / Pair Matching 2

· · 题解

质量还行的线段树优化 DP。

手膜样例不难发现，一张牌在和另一张牌匹配后，中间不能再有匹配的牌了，因为这样会把前一个匹配的牌挤出左手。同时因为只有两只手，所以不能同时匹配三张及以上的牌。

因此对于任意两对匹配的牌，只可能有两种关系：

于是设计 DP：dp_i 表示考虑前 i 位的最大答案。为了方便统计答案，我们强制匹配牌的贡献在右端点计算；与另一对牌相交的，以靠右的一对牌为准。那么有三类转移：

其中，pre_x 表示第一个 x 的位置。

前两种转移是容易的，考虑如何优化第三种转移。发现把有关 k 的变量提出来，是不含其它变量的，而对于有关 k 的两个不等限制，可以用一个类似二维数点的东西解决。但是我不会二维数点！

正着不好做，于是考虑反向计算，让每个 k 给会贡献到的 pre_{a_i} 做贡献。发现只要 pre_{a_k} <pre_{a_i}<k 的时候贡献就能被计算，因此维护一个求区间 \max，单点查的线段树，算贡献的时候把 [pre_{a_k},k] 区间贡献一个 dp_{pre_{a_k}}+V_k 即可。

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

#include <bits/stdc++.h>
#define lc (p<<1)
#define rc ((p<<1)|1)
using namespace std;
typedef long long ll;
const int N=1000005;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll n,a[N],b[N],dp[N],pre[N];
struct Node{
    int l,r;
    ll v,tag;
};
struct Segtree{
    Node tr[4*N];
    void pushup(int p)
    {
        tr[p].v=max(tr[lc].v,tr[rc].v);
    }
    void pushdown(int p)
    {
        if(tr[p].tag!=-inf)
        {
            tr[lc].tag=max(tr[lc].tag,tr[p].tag);
            tr[lc].v=max(tr[lc].v,tr[p].tag);
            tr[rc].tag=max(tr[rc].tag,tr[p].tag);
            tr[rc].v=max(tr[rc].v,tr[p].tag);           
        }
        tr[p].tag=-inf;
    }
    void build(int p,int ln,int rn)
    {
        tr[p]={ln,rn,-inf,-inf};
        if(ln==rn)return;
        int mid=(ln+rn)>>1;
        build(lc,ln,mid);
        build(rc,mid+1,rn);
        pushup(p);
    }
    void update(int p,int ln,int rn,ll x)
    {
        if(ln<=tr[p].l&&tr[p].r<=rn)
        {
            tr[p].v=max(tr[p].v,x);
            tr[p].tag=max(tr[p].tag,x);
            return;
        }
        pushdown(p);
        int mid=(tr[p].l+tr[p].r)>>1;
        if(ln<=mid)update(lc,ln,rn,x);
        if(rn>=mid+1)update(rc,ln,rn,x);
        pushup(p);
    }
    ll query(int p,int x)
    {
        if(tr[p].l==x&&tr[p].r==x)return tr[p].v;
        pushdown(p);
        int mid=(tr[p].l+tr[p].r)>>1;
        if(x<=mid)return query(lc,x);
        else return query(rc,x);
    }
}tr1;
int main()
{
//  freopen("smash.in","r",stdin);
//  freopen("smash.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=2*n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    memset(dp,-0x3f,sizeof(dp));
    dp[0]=0;
    tr1.build(1,1,2*n);
    for(int i=1;i<=2*n;i++)
    {
        dp[i]=max(dp[i],dp[i-1]);
        if(pre[a[i]])
        {
            dp[i]=max(dp[i],tr1.query(1,int(pre[a[i]]))+b[a[i]]);
            dp[i]=max(dp[i],dp[pre[a[i]]]+b[a[i]]);
            tr1.update(1,pre[a[i]],i,dp[pre[a[i]]]+b[a[i]]);
        }
        pre[a[i]]=i;
    }
    cout<<dp[2*n];
    return 0;
}