[洛谷春令营 省选第一次模拟T2] 最长不下降子序列【二分+归并排序】

• 2018-02-15
• 0
• 0

Problem:

题目描述

给出一个长度为 n 的整数序列，你能够使用的操作只有 rev(l, r)，表示将闭区间 [l, r] 内的数字翻转，需要的代价是 r-l+1，你需要在 4×10⁶ 的代价内最大化最终序列的 LIS 长度，LIS 表示最长不下降子序列。

只有你使用的操作的代价不超过限制，并且最终得到的序列的 LIS 和理论上能够得到的最大值一样的时候，才可以得分。

输入输出格式

输入格式：

第一行一个整数 n 表示序列长度。

接下来一行 n 个整数，表示序列。

输出格式：

输出第一行一个整数，表示使用的操作的数量。

接下来输出若干行操作，每行两个整数 l, r，表示一次操作。

如果有多种方案，输出任意一种即可。

输入输出样例

输入样例#1：

5
3 2 1 5 4

输出样例#1：

2
1 3
4 5

说明

对于所有数据，满足 n≤32000，0≤序列中的数字≤32000

Subtask1[10pts]

n≤100

Subtask2[10pts]

n≤1000

Subtask3[10pts]

0≤序列中的数字≤5

Subtask4[10pts]

无特殊限制

Solution:

# 我的 Code 竟然跑了 rank 1 !!! #

本题题目叫作“最长不下降子序列”，但是实际上是道排序题。

直接用 O(n²) 的冒泡排序，将交换看作长度为 2 的序列翻转，就可以水到 30 分。。（我不会告诉你比赛的时候我就是这么做的。。）

所以我们考虑基于 log 级别分治的归并排序。

显然直接二路归并不能支持翻转操作。。

我们考虑 01 归并，即将两个有序 01 序列合并时的情景：

• => 0 0 0 0 1 1 1 1 1 1|0 0 0 0 0 0 1 1 1 1
• => 0 0 0 0[1 1 1 1 1 1 0 0 0 0 0 0]1 1 1 1
• => 0 0 0 0[0 0 0 0 0 0 1 1 1 1 1 1]1 1 1 1
• => 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1

除去子序列为全 0 或全 1 时的特判，每次合并都可以看成一次区间翻转。

我们二分枚举值域内的值，把大于该值的数看作 1，小于等于该值的数看作 0。

那么就可以通过 log 级别次 01 归并的翻转操作来实现升序排列。

最大代价与时间复杂度相同，卡满为 0.5nlog²n ≈ 3583596 < 4×10⁶。（归并排序自带常数 0.5）

Code: O(nlog²n) [3402K, 40MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

inline void getint(int &num){
	char ch;
	while(!isdigit(ch = getchar()));
	num = ch - '0';
	while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}

int n, a[32005];
int ansl[4000000], ansr[4000000], ans = 0;

inline void Merge_Sort(int a[], int l, int r, int key){
	if(l >= r) return;
	int mid = l + r >> 1;
	Merge_Sort(a, l, mid, key);
	Merge_Sort(a, mid + 1, r, key);
	
	int revl, revr;
	for(revl = l; a[revl] <= key && revl <= mid; revl++);
	for(revr = mid + 1; a[revr] <= key && revr <= r; revr++);
	if(revl > mid || --revr <= mid) return;
	ansl[++ans] = revl, ansr[ans] = revr;
	for(; revl < revr; revl++, revr--) swap(a[revl], a[revr]);
}

inline void solve(int a[], int l, int r, int vl, int vr){
	if(l >= r || vl >= vr) return;
	int key = vl + vr >> 1;
	Merge_Sort(a, l, r, key);
	int mid = lower_bound(a + l, a + r + 1, key + 1) - a;  // Find the first larger one
	solve(a, l, mid - 1, vl, key);
	solve(a, mid, r, key + 1, vr);
}

int main(){
	getint(n);
	for(register int i = 1; i <= n; i++) getint(a[i]);
	solve(a, 1, n, -1, 32000);
	printf("%d\n", ans);
	for(register int i = 1; i <= ans; i++)
		printf("%d %d\n", ansl[i], ansr[i]);
	return 0;
}