优化动态规划

序列

首先要会最长上升子序列的转移，这里就不说了。

我们 \(i\) 位置的初始值为 \(a_i\)，可能变成的最大值为 \(mx_i\)，可能变成的最小值为 \(mn_i\)。

然后如果 \(j\) 要转移到 \(i\)，则需要满足：\(j<i,mx_j\le a_i,a_j\le mn_i\)。然后考虑把 \([l,mid]\) 按照 \(mx\) 排序，使得如果出现 \(j\) 满足 \(mx_j>a_i\) 那么 \([l,j-1]\) 是一个极大的区间满足这个区间的数全部满足前两个要求（因为 \(mx\) 单调不降）。还有就是，因为 \([mid+1,r]\) 按照 \(a\) 排序，所以可以保证如果对于区间 \([l,j]\) 的 \(mx\) 值全部不大于 \(i\) 的 \(a\) 值，那么对于 \(k>i\) 也不会出现 \(mx\) 值更大的情况，所以转移是对的。

然后就是怎么转移，大概就是把 \(j\) 的 \(f\) 值扔进树状数组，到转移的时候查一下 \(a\) 值不大于当前点 \(mn\) 值的点的最大 \(f\) 值进行转移（\(f\) 是动态规划转移数组）。

最后看一下代码：

#include<bits/stdc++.h>
#define int long long
#define N 100005
#define lim 100000
using namespace std;
int n,m,a[N],mx[N],mn[N],f[N],p[N],c[N];
bool cmp1(int x,int y){
	return mx[x]<mx[y];
}
bool cmp2(int x,int y){
	return a[x]<a[y];
}
int lowbit(int x){
	return x&-x;
}
void modify(int x,int v){
	while(x<=lim){
		c[x]=max(c[x],v);
		x+=lowbit(x);
	}
}
int qry(int x){
	int res=0;
	while(x){
		res=max(res,c[x]);
		x-=lowbit(x);
	}
	return res;
}
void clear(int x){
	while(x<=n){
		c[x]=0;
		x+=lowbit(x);
	}
}
void cdq(int l,int r){
	if(l==r){
		f[l]=max(f[l],1ll);
		return;
	}
	int mid=l+r>>1;
	cdq(l,mid);
	for(int i=l;i<=r;i++){
		p[i]=i;
	}
	sort(p+l,p+mid+1,cmp1);
	sort(p+mid+1,p+r+1,cmp2);
	int j=l;
	for(int i=mid+1;i<=r;i++){
		while(j<=mid&&mx[p[j]]<=a[p[i]]){
			modify(a[p[j]],f[p[j]]);
			j++;
		}
		f[p[i]]=max(f[p[i]],qry(mn[p[i]])+1);
	}
	for(int i=l;i<=mid;i++){
		clear(a[i]);
	}
	cdq(mid+1,r);
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		mx[i]=mn[i]=a[i];
	}
	while(m--){
		int x,y;
		cin>>x>>y;
		mx[x]=max(mx[x],y);
		mn[x]=min(mn[x],y);
	}
	cdq(1,n);
	int res=0;
	for(int i=1;i<=n;i++){
		res=max(res,f[i]);
	}
	cout<<res;
	return 0;
}