TJOI2016序列

TJOI
BIT, dp, 分治, 树套树

TJOI2016 序列

题目大意：

有一个数列，数列中某些项的值可能会变化，但同一个时刻最多只有一个值发生变化。

能否选出一个子序列，使得在任意一种变化中，这个子序列都是不降的？求这个子序列的最长长度。

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

题解：

首先，因为是对任意的变化都满足子序列不降，因而每一个位置上的数字我们只用存它原来的大小，变化后的最大值，以及变化后的最小值。（如果最大、最小都可以满足，其他的值也一定可以满足）

于是，我们发现，题目变成了比较明显的dp。

定义$dp_i$ 表示以i为结尾的最长的合法子序列有多长。

那么转移方程就是$dp_i = max \{ dp_j \} +1 $

看起来与LIS十分相似，不过转移条件变得更加苛刻了：

$num_j \le mi_i $ 并且 $ mx_j \le num_i $ .

不难发现，除去下标这一维，我们还剩下两个维度需要维护。

比较显然的想法是利用树套树来维护这两个维度。

由于本题维护的是前缀最大值，因而可以用二维BIT来实现。

但不能用一般的二维BIT，那样子空间开不下。

我们发现，总共的状态数为n个，我们开$n^2$显然是冗余了。

因为每一个状态的位置已经固定，我们可以在一维BIT基础上，开一个动态数组来维护第二维。

那么每一次修改或查询前，先二分一下对应位置即可。(相当于把它离散了)

总的时间复杂度为$O(nlog^2n)$ 。

具体实现可以看代码。

Code（二维BIT）:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<vector>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
inline void Rd(int&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
}
const int N=100002;
int n,m,num[N],mx[N],mi[N],dp[N];
inline void Min(int&a,int b){
	if(a>b)a=b;
}
inline void Max(int&a,int b){
	if(a<b)a=b;
}
#define lowbit(x) (x&(-x))
struct Binary_Indexed_Tree{
	int sz;
	vector<int>data,bit;
	void insert(int x){
		data.push_back(x);
	}
	void prepare(){
		sort(data.begin(),data.end());
		data.erase(unique(data.begin(),data.end()),data.end());
		sz=data.size();
		bit.resize(sz+1,0);
	}
	void add(int x,int v){
		x=upper_bound(data.begin(),data.end(),x)-data.begin();
		if(!x)return;
		for(;x<=sz;x+=lowbit(x))
			Max(bit[x],v);
	}
	int sum(int x){
		x=upper_bound(data.begin(),data.end(),x)-data.begin();
		if(!x)return 0;
		int res=0;
		for(;x>0;x-=lowbit(x))
			Max(res,bit[x]);
		return res;
	}
};
struct Fenwick_Tree{
	Binary_Indexed_Tree bit[N];
	void insert(int x,int y){
		for(;x<N;x+=lowbit(x))
			bit[x].insert(y);
	}
	void prepare(){
		for(int i=1;i<N;i++)
			bit[i].prepare();
	}
	void add(int x,int y,int v){
		for(;x<N;x+=lowbit(x))
			bit[x].add(y,v);
	}
	int sum(int x,int y){
		int res=0;
		for(;x>0;x-=lowbit(x))
			Max(res,bit[x].sum(y));
		return res;
	}
}T;
int main(){
	Rd(n),Rd(m);
	for(int i=1;i<=n;i++){
		Rd(num[i]);
		mi[i]=mx[i]=num[i];
	}
	for(int i=1,a,b;i<=m;i++){
		Rd(a),Rd(b);
		Min(mi[a],b);
		Max(mx[a],b);
	}
	for(int i=1;i<=n;i++)
		T.insert(num[i],mx[i]);
	T.prepare();
	for(int i=1;i<=n;i++){
		dp[i]=T.sum(mi[i],num[i])+1;
		T.add(num[i],mx[i],dp[i]);
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		Max(ans,dp[i]);
	printf("%d\n",ans);
	return 0;
}

另外还有一种实际跑起来更加优秀的算法：

这是一种分治的算法。

对于当前想要求解的区间$[L,R]$ 的dp值，我们先递归求解$[L,mid]$ 的dp值，再用$[L,mid]$ 区间的dp值去更新$[mid+1,R]$ 区间的dp值。最后递归求解$[mid+1,R]$ 的dp值。

(考虑一下树的中序遍历)

这样可以保证下标的一维已经满足。(保证了所有下标比我小的点都有机会更新我)

那么，重点来看更新操作。

我们用左半边区间，去更新右半边。

由于已经保证所有下标比我小的点都有机会更新我，我们可以在此离线操作。

可以把左半边的值都看作是update，而把右半边的值都看作query。

我们把update和query放到一起，以第一维为关键词排序，这样可以保证一维一定满足。

(若相同，update要放到query前面，因为此update也可更新到后面的query)

那么，最后就只剩下一维了，我们用一个BIT来维护前缀最大值即可。

总的时间复杂度为$O(nlog^2n)$ 。

但实际效果比二维BIT要优秀许多。

Code（分治）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
inline void Rd(int&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
}
inline void Min(int&a,int b){
	if(a>b)a=b;
}
inline void Max(int&a,int b){
	if(a<b)a=b;
}
const int N=100005;
int n,m,num[N],mi[N],mx[N],dp[N];
struct Bit{
	#define lowbit(x) (x&(-x))
	int bit[N];
	void add(int x,int v){
		for(;x<N;x+=lowbit(x))Max(bit[x],v);
	}
	void del(int x){
		for(;x<N;x+=lowbit(x))bit[x]=0;
	}
	int sum(int x){
		int res=0;
		for(;x>0;x-=lowbit(x))Max(res,bit[x]);
		return res;
	}
}T;
struct Action{
	int op,id,num1,num2;
	//op=0表示update
	//op=1表示query 
	bool operator <(const Action&tmp)const{
		if(num1!=tmp.num1)return num1<tmp.num1;
		return op<tmp.op;
	}
}act[N];
void update(int L,int R){
	int tot=0,mid=L+R>>1;
	for(int i=L;i<=mid;i++)act[++tot]=(Action){0,i,mx[i],num[i]};
	for(int i=mid+1;i<=R;i++)act[++tot]=(Action){1,i,num[i],mi[i]};
	sort(act+1,act+1+tot);
	for(int i=1;i<=tot;i++){
		if(act[i].op==0)T.add(act[i].num2,dp[act[i].id]);
		else Max(dp[act[i].id],T.sum(act[i].num2)+1);
	}
	for(int i=1;i<=tot;i++)
		if(act[i].op==0)T.del(act[i].num2);
}
void solve(int L,int R){
	if(L==R){
		Max(dp[L],1);
		return;
	}
	int mid=L+R>>1;
	solve(L,mid);
	update(L,R);
	solve(mid+1,R);
}
int main(){
	Rd(n),Rd(m);
	for(int i=1;i<=n;i++){
		Rd(num[i]);
		mi[i]=mx[i]=num[i];
	}
	for(int i=1,a,b;i<=m;i++){
		Rd(a),Rd(b);
		Min(mi[a],b);
		Max(mx[a],b);
	}
	solve(1,n);
	int ans=0;
	for(int i=1;i<=n;i++)
		Max(ans,dp[i]);
	printf("%d\n",ans);
	return 0;
}
分享到 评论