P8277 [USACO22OPEN] Up Down Subsequence P

模拟赛的题，但是没做，所以现在来补。

题目简介

题目名称：

题目来源：

评测链接：https://www.luogu.com.cn/problem/P8277

形式化题意：存在一个长度为的排列，以及一个长度为的由 U 和 D 组成的字符串，求一个的子序列，满足当时，，当时满足，求最大的。

数据范围：

首先提一嘴部分分，是一个的求的做法，之前一直没有整的一块漏洞。

最长上升子序列的优化

有一个众所周知的求法：

f_{i} = (max_{j < i, a_{j} < a_{i}} f_{j}) + 1

但这样做显然是不优美的，所以考虑优化。

贪心与二分结合

考虑当前 $i$ 如果有多个选择，我们肯定选择 $a_{i}$ 最小的那一个，毕竟这样的话后面能选的概率就更大。

我们将当前构造出的 $LIS$ 记为 $d p ()$ ，其中 $d p (i)$ 就表示当前 $LIS$ 的第 $i$ 位。对于我们现在需要加入的第 $x$ 位，我们找到 $d p ()$ 中第一个比 $a_{x}$ 大的数，并将其替换为 $a_{x}$ ，而如果没有的话，就将 $a_{x}$ 添加到 $d p ()$ 的末尾，最终答案就是 $d p ()$ 的长度，而 $d p ()$ 本身也是构造的一组解。

参考实现

int len=1;
Dp[1]=a[1];
for(int i=2;i<=n;++i)
{
    if(a[i]>Dp[len]) Dp[++len]=a[i];
    else Dp[std::lower_bound(Dp+1,Dp+len+1)-Dp]=a[i];
}
std::cout<<len<<std::endl;
for(int i=1;i<=len;++i) std::cout<<Dp[i]<<" ";
return 0;

这个是常数最小的做法。

树状数组优化dp

考虑 $LIS$ 的本质就是一串逐渐变大的数字，所以我们考虑将 $a_{i}$ 从小到大依次填入。记录 $i d (x)$ 表示 $a_{x}$ 在原序列里的位置。

每当我们要插入数 $a_{i}$ 的时候，查询 $[1, i d (i))$ 之间已经维护到的最大值，也就是当前我们已知的最大 $LIS$ 长度，然后我们在 $i d (i)$ 处将其 $+ 1$ 就可以得到插入了 $a_{i}$ 之后的答案，最后的答案就是 $[1, n]$ 的最大值。

这里我们需要一个能够高效维护单点修改以及前缀查询最大值的数据结构，树状数组当然是首选，线段树和分块肯定也可以，但是效率提不起来。

参考实现

struct Node
{
    int val,id;
    bool operator<(const Node &x) const { return val<x.val; }
}a[MAXN];
int main()
{
    for(int i=1;i<=n;++i) read(a[i].val),a[i].id=i;
    std::sort(a+1,a+n+1);
    for(int i=1;i<=n;++i) Tr.add(a[i].id,Tr.query(a[i].id)+1);
    std::cout<<Tr.query(n)<<std::endl;
    return 0;
}

当然，如果不记录 $i d ()$ 也是可以的，此时的 $BIT$ 维护值域。

参考实现

for(int i=1;i<=n;++i) Tr.add(a[i],Tr.query(a[i]-1)+1),maxa=std::max(maxa,a[i]);
std::cout<<Tr.query(maxa)<<std::endl;
return 0;

本质在于 $LIS$ 的求解可以视作一个二维偏序问题。

考虑用 $f_{i}$ 表示在 $a$ 序列中以 $i$ 结尾能够最大匹配的 $b$ 序列的长度。

考虑 $f_{i}$ 的转移：

f_{i} = {\begin{cases} max f_{j} + 1 & , b_{f_{j} + 1} = U, a_{j} < a_{i} \\ max f_{j} + 1 & , b_{f_{j} + 1} = D, a_{j} > a_{i} \end{cases}

然后发现的转移和有关，所以没有办法优化，时间复杂度固定在，所以考虑换一个思路。

记录表示以结尾且假设，同理。

那么的转移就变成了：

f_{i} = {\begin{cases} max U_{j} + 1 & , a_{j} < a_{i} \\ max D_{j} + 1 & , a_{j} > a_{i} \end{cases}

然后问题在于怎么维护，当的时候，，否则。容易发现需要维护单点修改和前后缀最大值，所以用线段树或者都可以。

AC Code

// ----- Eternally question-----
// Problem: P8277 [USACO22OPEN] Up Down Subsequence P
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8277
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-07-11 16:51:25
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=3e5+10;
const int INF=0x3f3f3f3f;
int N,a[MAXN];
char b[MAXN];
struct Segment
{
	#define ls (p<<1)
	#define rs (p<<1|1)
	int Tr[MAXN<<2],Len;
	inline void build(int n)
	{
		Len=1;
		while(Len<=n+1) Len<<=1;
	}
	inline void modifyX(int x,int v)
	{
		Tr[x+Len]=v;
		for(int p=(x+Len)>>1;p;p>>=1) Tr[p]=std::max(Tr[ls],Tr[rs]);
	}
	inline int queryMax(int l,int r)
	{
		if(l>r) return -INF;
		int res=-INF;
		for(l+=Len-1,r+=Len+1;l^r^1;l>>=1,r>>=1)
		{
			if(~l&1) checkMax(res,Tr[l^1]);
			if(r&1) checkMax(res,Tr[r^1]);
		}
		return res;
	}
	#undef ls
	#undef rs
}Up,Down;
int Dp[MAXN],ans;
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i) read(a[i]);
	scanf("%s",b+1);
	Up.build(N),Down.build(N);
	for(int i=1;i<=N;++i)
	{
		Dp[i]=std::max(Up.queryMax(1,a[i]-1),Down.queryMax(a[i]+1,N))+1;
		if(b[Dp[i]]=='U') Up.modifyX(a[i],Dp[i]);
		else Down.modifyX(a[i],Dp[i]);
		checkMax(ans,Dp[i]);
	}
	write(ans-1);
	return 0;
}
/*

*/