COCI2021-2022#1 Volontiranje

P7931 [COCI2021-2022#1] Volontiranje

题目大意

给你一个$1\sim n$的排列$p$，要求从这里面取出尽可能多的没有交集的上升子序列，且他们的长度等于原排列的最长上升子序列的长度。

输出这些上升子序列的个数，长度，以及每个子序列中每个元素的下标。

$1\le n\le 10^6$

题解

求以序列中每个数结尾的最长上升子序列，可以用树状数组，也可以用这个方法，都是$O(n\log n)$的。

下面考虑如何求方案数和每种方案。

我们可以把题目所给序列中的每个元素的下标和值在平面直角坐标系中表示成一个点，并将这些点分层，第$k$层的点中的每一个点$i$都满足以序列中第$i$个数结尾的最长上升子序列的长度为$k$。

题目第三个样例的分层结果如下：

那么问题就转换成了在每层中选一个点，满足它们的横坐标和纵坐标递增，且每个点最多被选一次，求最多能选几个序列。

有一点我们需要知道：当从一层到下一层时，选择下标小的点不劣于选择下标大的点。

比如这个图，在选到$A$时，如果选$D$，则$C$就不能再选了；但如果选$B$，那$C$可以选$D$，显然更优。

也可以自己举几个例子来理解。

时间复杂度为$O(n\log n)$。

一些细节

注意如果使用$vector$的话，在删除$vector$最前面的数的时候要用到$v.erase(v.begin())$，这是很慢的。可以将每个$vector$首尾翻转，那么删除最前面的数变为删除最后面的数，用$v.pop\_back()$即可，这样会快很多。如果$TLE$的话，可以进行这样的修改。

code

#include
using namespace std;
int n,ans1=0,ans2=0,a[1000005],f[1000005],tr[1000005];
vector<int>v[1000005],ans[1000005];
vector<int>::iterator it;
int lb(int i){
	return i&(-i);
}
void pt(int i,int v){
	while(i<=n){
		tr[i]=max(tr[i],v);
		i+=lb(i);
	}
}
int find(int i){
	int re=0;
	while(i){
		re=max(re,tr[i]);
		i-=lb(i);
	}
	return re;
}
void dd(){
	while(1){
		if(ans[ans1].empty()){
			if(v[1].empty()) break;
			else{
				ans[ans1].push_back(v[1].back());
				v[1].pop_back();
			}
		}
		else if(ans[ans1].size()==ans2) ++ans1;
		else{
			int t=ans[ans1].size()+1,w=ans[ans1].back();
			while(!v[t].empty()&&v[t].back()<w) v[t].pop_back();
			if(v[t].empty()||a[w]>a[v[t].back()]) ans[ans1].pop_back();
			else{
				ans[ans1].push_back(v[t].back());v[t].pop_back();
			}
		}
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		f[i]=find(a[i])+1;
		pt(a[i],f[i]);
		ans2=max(ans2,f[i]);
		v[f[i]].push_back(i);
	}
	for(int i=1;i<=ans2;i++){
		reverse(v[i].begin(),v[i].end());
	}
	dd();
	printf("%d %d\n",ans1,ans2);
	for(int i=0;i<ans1;i++){
		for(int j=0;j<ans2;j++){
			printf("%d ",ans[i][j]);
		}
		printf("\n");
	}
	return 0;
}
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