Luogu P11727 [JOIG 2025] 神経衰弱 2 / Pair Matching 2 题解 [ 蓝 ] [ 线性 DP ] [ 线段树 ]

神経衰弱 2 / Pair Matching 2：质量还行的线段树优化 DP。

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

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

• 相交关系。且一对匹配的牌最多只能和另一对匹配的牌相交。
• 不交关系。

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

• 继承状态：\(dp_i=\max(dp_i,dp_{i-1})\)。
• 与其他对匹配的牌不交的转移：\(dp_i=\max(dp_i,dp_{pre_{a_i}}+V_{a_{i}})\)。
• 与某一对牌相交的转移：\(dp_i =\max(dp_i,dp_{pre_{a_k}}+V_{a_k}+V_{a_i})\)。其中 \(a_k\) 是某一对经过了 \(pre_{a_i}\) 的牌，即 \(pre_{a_k}<pre_{a_i}<k <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;
}