• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

洛谷 P4093 [HEOI2016/TJOI2016]序列 CDQ分治优化DP

开发技术 开发技术 3周前 (09-08) 17次浏览

洛谷 P4093 [HEOI2016/TJOI2016]序列 CDQ分治优化DP

题目描述

佳媛姐姐过生日的时候,她的小伙伴从某宝上买了一个有趣的玩具送给他。

玩具上有一个数列,数列中某些项的值可能会变化,但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性,她想请教你,能否选出一个子序列,使得在任意一种变化中,这个子序列都是不降的?请你告诉她这个子序列的最长长度即可。

输入格式

输入的第一行有两个正整数 (n,m),分别表示序列的长度和变化的个数。

接下来一行有 (n) 个整数,表示这个数列原始的状态。

接下来 (m) 行,每行有 (2) 个整数 (x,y),表示数列的第 (x) 项可以变化成 (y) 这个值。

输出格式

输出一个整数,表示对应的答案。

输入输出样例

输入 #1

3 4
1 2 3
1 2
2 3
2 1
3 4

输出 #1

3

说明/提示

注意:每种变化最多只有一个值发生变化。

在样例输入中,所有的变化是:

1 2 3
2 2 3
1 3 3
1 1 3
1 2 4

选择子序列为原序列,即在任意一种变化中均为不降子序列。

对于 (20%) 数据,所有数均为正整数,且小于等于 (300)

对于 (50%) 数据,所有数字均为正整数,且小于等于 (3000)

对于 (100%) 数据,所有数字均为正整数,且小于等于 (10^5)(1le xle n)

分析

我们设(min[i])为处在位置(i)上的数变化得到的最小值,(max[i])为处在位置(i)上的数变化得到的最大值,(f[i])为以(i)结尾的最长上升子序列的长度

(f[i]=max(f[i],f[j]+1),j<i,max[j] leq i,min[i] geq j)

我们会发现这是一个三位偏序问题,可以用(CDQ)分治优化

代码

#include<cstdio>
#include<algorithm>
#include<iostream>
inline int read(){
	int x=0,fh=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=1e6+5;
int f[maxn],a[maxn],mmax[maxn],mmin[maxn],tr[maxn],n,m;
int lb(int xx){
	return xx&-xx;
}
void ad(int wz,int val){
	for(int i=wz;i<maxn;i+=lb(i)){
		tr[i]=std::max(tr[i],val);
	}
}
int cx(int wz){
	int ans=0;
	for(int i=wz;i>0;i-=lb(i)){
		ans=std::max(tr[i],ans);
	}
	return ans;
}
void qk(int wz){
	for(int i=wz;i<maxn;i+=lb(i)){
		tr[i]=0;
	}
}
int tot=1,id[maxn];
bool cmp1(int aa,int bb){
	return a[aa]<a;
}
bool cmp2(int aa,int bb){
	return mmin[aa]<mmin;
}
void solve(int l,int r){
	if(l==r) return;
	int mids=(l+r)>>1;
	solve(l,mids);
	for(int i=l;i<=r;i++) id[i]=i;
	std::sort(id+l,id+mids+1,cmp1);
	std::sort(id+mids+1,id+r+1,cmp2);
	int now=l;
	for(int i=mids+1;i<=r;i++){
		while(a[id[now]]<=mmin[id[i]] && now<=mids){
			ad(mmax[id[now]],f[id[now]]);
			now++;
		}
		f[id[i]]=std::max(f[id[i]],cx(a[id[i]])+1);
		tot=std::max(tot,f[id[i]]);
	}
	for(int i=now-1;i>=l;i--){
		qk(mmax[id[i]]);
	}
	solve(mids+1,r);
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		mmax[i]=mmin[i]=a[i];
		f[i]=1;
	}
	for(int i=1;i<=m;i++){
		int aa,bb;
		aa=read(),bb=read();
		mmax[aa]=std::max(mmax[aa],bb);
		mmin[aa]=std::min(mmin[aa],bb);
	}
	solve(1,n);
	printf("%dn",tot);
	return 0;
}

喜欢 (0)