Problem Description

Given a sequence of numbers A=a1,a2,…,aN, a subsequence b1,b2,…,bk of A is referred as increasing if b1<b2<…<bk. LY has just learned how to find the longest increasing subsequence (LIS). Now that he has to select L consecutive numbers and remove them from A for some mysterious reasons. He can choose arbitrary starting position of the selected interval so that the length of the LIS of the remaining numbers is maximized. Can you help him with this problem?

Input

The first line of input contains a number T indicating the number of test cases (T≤100). For each test case, the first line consists of two numbers N and L as described above (1≤N≤100000,0≤L≤N). The second line consists of N integers indicating the sequence. The absolute value of the numbers is no greater than \(10^9\). The sum of N over all test cases will not exceed 500000.

Output

For each test case, output a single line consisting of “Case #X: Y”. X is the test case number starting from 1. Y is the maximum length of LIS after removing the interval.

Sample Input

Sample Output

1 2	Case #1: 3 Case #2: 1

Source

2015 ACM/ICPC Asia Regional Hefei Online

Key

啊被这题折磨了两天。最后发现是我数据范围错了。。题目说“The absolute value of the numbers is no greater than \(10^9\)”，我理解成\([1,1^9)\)了。。。

LIS题的一个变种。用\(O(n^2)\)的DP做是没法做的，\(O(n^2)\)本身就超时了，更别说别的处理。得用\(O(n \log n)\)的那个算法。

基本思路是，先计算出以每个\(A[i]\)为开头的LIS（即从右向左找以\(A[i]\)结尾的最大降序子序列）。然后枚举所有挖掉的连续字串的位置：对于挖掉的\([i-L, i-1]\) \((i>L)\)，LIS最大值为右侧以\(A[i]\)打头时的LIS加上左侧以比\(A[i]\)小的值结尾的最大LIS。

于是关键是怎么在左侧找出一个以\(A[i-L-1]\)结尾的LIS，要求LIS尽量大且\(A[i-L-1]<A[i]\)。查了题解，才知道可以利用那个\(O(n \log n)\)算法，二分找出在左侧x个值中小于A[i]的最大LIS。真是太强了。

Code

#include<functional>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int Maxn = 100000 + 10;

int T, N, L;
int A[Maxn], LIS[Maxn], BG[Maxn];

int main() {
	//freopen("F:\\Projects\\ConsoleApplication2\\ConsoleApplication2\\in.txt", "r", stdin);
	//freopen("F:\\Projects\\Debug Tools\\Comparison1.txt", "w", stdout);
	ios::sync_with_stdio(false);
	cin >> T;
	for (int Case = 1; Case <= T; ++Case) {
		cin >> N >> L;
		for (int i = 0; i < N; ++i) {
			cin >> A[i];
		}

		int res = 0;
		int len, idx;
		len = 1;
		LIS[0] = 0x7fffffff;
		for (int i = N - 1; i >= 0; --i) {
			idx = lower_bound(LIS, LIS + len, A[i], greater<int>()) - LIS;
			if (idx == len) ++len;
			LIS[idx] = A[i];
			BG[i] = idx;
			if (i >= L) res = max(res, idx);
		}

		len = 1;
		LIS[0] = 0x80000000;
		for (int i = L; i < N; ++i) {
			idx = lower_bound(LIS, LIS + len, A[i], less<int>()) - LIS;
			res = max(res, BG[i] + idx - 1);

			idx = lower_bound(LIS, LIS + len, A[i - L], less<int>()) - LIS;
			if (idx == len) ++len;
			LIS[idx] = A[i - L];
			res = max(res, idx);
		}

		printf("Case #%d: %d\n", Case, res);
	}
	return 0;
}

XieNaoban's Blog

ACM ICPC 2015合肥网络赛 - Removed Interval