Up Down Subsequence P 题解

思路

首先还是要推出正常的 DP 方程，它应该是 $n$ 个状态 $O(n^2)$ 复杂度的。个人是正推的这个式子，即：（懒得写状态转移方程直接摆代码了）

if(str[f[i]+1] == 'U'){
  if(arr[j] > arr[i]){
    f[j] = max(f[j],f[i] + 1); 
  }
}else{
  if(arr[j] < arr[i]){
    f[j] = max(f[j],f[i] + 1);
  }
}

考虑逆推，相当于每次算出一个 $f_i$ 就是插入了一个转移，如果 $f_i$ 对应的字符为 U，那么相当于在一个转移序列 up 中插入了 $(arr_i,f_i+1)$，意思是如果有一个数 $u$ 满足 $arr_u \gt arr_i$，那么 $f_u$ 可以用 $f_i+1$ 更新；如果对应字符为 D，那么就是在反过来的 down 中插入同样的值。

显然，如果 up 中存在 $(a,b)$，$(c,d)$ 满足 $a \lt c$ 且 $b \ge d$ 那么后者显然不如前者优（可以更新的范围更小，值还更差），那么我们直接弹出。反之 down 也是同理。

于是我们维护两个单调的转移序列（不知道该怎么叫......）up，down，它们的键值对 $(key,val)$ 满足 $key$ 单调递增（反过来当然也可以），$val$ 单调递减。每次转移从这两个转移序列转移，然后把新的 $arr_i,f_i+1$ 插入，然后向右边（或者左边）检测是否不满足单调性，如果是的话则删除。

这个序列使用 set 维护，总复杂度 $O(n \log n)$：转移就使用 lower_bound，显然 $O(\log n)$，而删除操作单次最多 $O(\log n)$，由于一次转移只插入一个值，均摊下来删除操作也是 $O(\log n)$的。

另外很神奇的一点是，咱的代码其实有一点小问题，只用新的转移弹掉不满足单调性的旧的转移，却没有检查新的转移是否不满足单调性。也许新的转移一定更优？不清楚了

代码

#include<bits/stdc++.h>
#define Akano 1
#define pure__Elysia 0
#define loves ^
using namespace std;
const int MAXN = 3e5 + 1018 + 1108;
int n,arr[MAXN],f[MAXN];
string str;
set<pair<int,int> > up,down;
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i = 1;i <= n;i++)cin>>arr[i];
	cin>>str;
	str = "." + str;
	for(int i = 1;i <= n;i++){
		auto it1 = up.lower_bound(make_pair(arr[i],0));
		if(it1 != up.begin()){
			it1--;
			f[i] = max(f[i],(*it1).second);
		}
		auto it2 = down.upper_bound(make_pair(arr[i],0));//upper,lower应该一样的
		if(it2 != up.end()){
			f[i] = max(f[i],(*it2).second);
		}
		if(str[f[i]+1] == 'U'){
			auto it = up.insert(make_pair(arr[i],f[i]+1)).first;
			while(true){
				auto nxt = it;
				nxt++;
				if(nxt == up.end())break;
				if((*nxt).second <= f[i] + 1){
					up.erase(nxt);
				}else{
					break;
				}
			}
		}else{
			auto it = down.insert(make_pair(arr[i],f[i]+1)).first;
			while(it != down.begin()){
				auto pre = it;
				pre--;
				if((*pre).second <= f[i] + 1){
					down.erase(pre);
				}else{
					break;
				}
			}
		}
	}
	int ans = 0;
	for(int i = 1;i <= n;i++){
		ans = max(ans,f[i]);
	}
	cout<<ans;
	return not(Akano loves pure__Elysia);
}