题解 P4093 [HEOI2016/TJOI2016]序列

Solution

这显然是求 \(\mathsf{LIS}\) 的模板多了一维限制，转移方程为 \(f_i=\max\limits_{j<i,a_i\ge mx_j,mn_i\ge a_j}f_j+1\)，其中 \(f_i\) 表示以 \(i\) 结尾的最长子序列，\(mx_i,mn_i\) 表示 \(a_i\) 能变化到的最大值和最小值，因为介于 \(mx_i\) 和 \(mn_i\) 之间的数都没有用。

对于方程的这三个限制，可以当三维偏序来做，每次用 \(f_i\) 更新 \((a_i,mx_i)\) 矩形内的最大值，查询时查 \((mn_i,a_i)\) 内的最大值即可。

实现的话，可以用 \(\mathsf{CDQ}\) 分治或树套树，这里我用了二维树状数组，用 pb_ds 的哈希表 gp_hash_table 来实现类似的动态开点。

Code

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
const int N=1e5+5;
int n,m,mv,ans,a[N],mn[N],mx[N];
gp_hash_table<int,int>c[N];
inline void add(int x,int y,int v){
	for(int i=x;i<=mv;i+=i&-i)
		for(int j=y;j<=mv;j+=j&-j)
			c[i][j]=max(c[i][j],v);
}
inline int ask(int x,int y){
	int res=0;
	for(int i=x;i;i-=i&-i)
		for(int j=y;j;j-=j&-j)
			res=max(res,c[i][j]);
	return res;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",a+i),mv=max(mv,mx[i]=mn[i]=a[i]);
	for(int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y);
		mx[x]=max(mx[x],y);
		mn[x]=min(mn[x],y);
		mv=max(mv,mx[x]);
	}
	for(int i=1;i<=n;i++){
		int res=ask(mn[i],a[i])+1;
		add(a[i],mx[i],res);
		ans=max(ans,res);
	}printf("%d\n",ans);
	return 0;
}

题解 P4093 [HEOI2016/TJOI2016]序列

原文：https://www.cnblogs.com/aday526/p/solution-p4093.html