【2023NOIP模拟赛22】摘抄文档 做题记录

给定两个长 $n$ 的序列 $a$ 和 $b$，每次操作可以选择一个满足 $1\le i<n$ 的 $i$ 并把 $a_i$ 和 $a_{i+1}$ 改为 $\max(a_i,a_{i+1})$，求任意次操作后 $\sum\limits_{i=1}^n[a_i=b_i]$ 的最大值。

$1\le n\le 10^5$，$1\le a_i,b_i\le 10^9$。

设操作完后的 $a$ 序列为 $a'$。

显然操作相当于每个 $a_i$ 不断往外拓展，设 $a_i$ 拓展成了 $a'_{[l_i,r_i]}$（没有任何 $a_j’$ 由 $a_i$ 拓展来则把 $a_i$ 删掉），那么有个结论：

• 一组 $[l_i,r_i]$ 合法当且仅当 $\forall i<j$ 都有 $r_i<l_j$，即区间不交且相对顺序和 $i$ 的相对顺序相同。

那么不妨设 $a'_i$ 是由 $p_i$ 拓展而来的，不难发现 $p_i$ 单调递增。

发现钦定 $a'_i=b_i$ 的所有 $i$ 都满足 $p_i$ 为 $\max\limits_{j\le i,a_j=b_i}\{j\}$ 或 $\min\limits_{j\ge i,a_j=b_i}\{j\}$ 并不影响答案，那么不妨设这两个位置分别为 $lb_i$ 和 $rb_i$（不存在则为 $-1$）。

又发现 $p_i$ 可以为 $lb_i$ 当且仅当 $lb_{i}\not=-1$ 且 $a_{[lb_i,i]}$ 中的最大值 $\le b_i$，可以为 $rb_i$ 同理。那么不妨把所有不合法的 $lb$ 和 $rb$ 都赋值为 $-1$。

那么不难发现 $i$ 对答案有贡献当且仅当：

• $lb_i\not= -1$ 且 $p_{i-1}\le lb_i$；
• $rb_i\not=-1$ 且 $p_{i-1}\le rb_i$；

因为 $lb_i\not=-1$ 和 $rb_i\not=-1$ 已经解决掉所有值域上的限制，只剩下 $[l_i,r_i]$ 相对顺序的限制。

那么考虑一个朴素的 dp：设 $f_{i,j}$ 表示处理完 $a'_{[1,i]}$ 且 $a'_i=a_j$ 时 $\sum\limits_{k=1}^i[a'_k=b_k]$ 的最大值。显然有转移：

$f_{i,j}=f_{i-1,j}\\ \text{若 }lb_i\not=-1,f_{i,lb_i}=\max\limits_{j\le lb_i}\{f_{i-1,j}\}+1\\ \text{若 }rb_i\not=-1,f_{i,rb_i}=\max\limits_{j\le rb_i}\{f_{i-1,j}\}+1$

发现可以用树状数组维护前缀 max 解决，时间复杂度 $O(n\log n)$。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int S=100005;

int n,a[S],b[S];
int m,tb[S*2];
int top,sta[S],pre[S],nxt[S];
int pos[S*2],lb[S],rb[S];
int c[S];

inline void add(int p,int val)
{
	for(int i=p;i<=n;i+=i&-i) c[i]=max(c[i],val);
}

inline int que(int p)
{
	int res=0;
	for(int i=p;i>=1;i-=i&-i) res=max(res,c[i]);
	return res;
}

int main()
{
	freopen("copy.in","r",stdin);
	freopen("copy.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++) tb[++m]=a[i],tb[++m]=b[i];
	sort(tb+1,tb+m+1);
	m=unique(tb+1,tb+m+1)-tb-1;
	for(int i=1;i<=n;i++)
	{
		a[i]=lower_bound(tb+1,tb+m+1,a[i])-tb;
		b[i]=lower_bound(tb+1,tb+m+1,b[i])-tb;
	}
	sta[top=0]=0;
	for(int i=1;i<=n;i++)
	{
		while(top>0&&a[sta[top]]<a[i]) top--;
		pre[i]=sta[top];
		sta[++top]=i;
	}
	sta[top=0]=n+1;
	for(int i=n;i>=1;i--)
	{
		while(top>0&&a[sta[top]]<a[i]) top--;
		nxt[i]=sta[top];
		sta[++top]=i;
	}
	for(int i=1;i<=m;i++) pos[i]=-1;
	for(int i=1;i<=n;i++)
	{
		pos[a[i]]=i;
		lb[i]=pos[b[i]];
		if(lb[i]!=-1&&nxt[lb[i]]<=i) lb[i]=-1;
	}
	for(int i=1;i<=m;i++) pos[i]=-1;
	for(int i=n;i>=1;i--)
	{
		pos[a[i]]=i;
		rb[i]=pos[b[i]];
		if(rb[i]!=-1&&pre[rb[i]]>=i) rb[i]=-1;
	}
	// for(int i=1;i<=n;i++) printf("%d %d\n",lb[i],rb[i]);
	for(int i=1;i<=n;i++)
	{
		if(rb[i]!=-1) add(rb[i],que(rb[i])+1);
		if(lb[i]!=-1&&lb[i]!=rb[i]) add(lb[i],que(lb[i])+1);
	}
	printf("%d\n",que(n));
	return 0;
}