1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime>10 #include <list>11 #include <set>12 #include <map>13 using namespace std;14 typedef long long LL;15 typedef pair <int, int> P;16 const int N = 1e5 + 5;17 int dp1[N], dp2[N], a[N], inf = 1e9 + 7;18 int y[N], x[N]; // y[i]表示以i下标为开头的LIS，x[i]表示以i为结尾的LIS19 20 int main()21 {22     int t, n, m;23     scanf("%d", &t);24     for(int ca = 1; ca <= t; ++ca) {25         scanf("%d %d", &n, &m);26         for(int i = 1; i <= n; ++i) {27             scanf("%d", a + i);28             dp1[i] = dp2[i] = inf;29         }30         dp2[0] = dp1[0] = inf;31         int ans = 0;    32         for(int i = n; i >= 1; --i) { //倒着求变负，求以i开头的LIS33             int pos = lower_bound(dp2, dp2 + n, -a[i]) - dp2;34             y[i] = pos + 1;35             //cout << y[i] << endl;36             dp2[pos] = -a[i];37             if(i == m + 1) {38                 ans = lower_bound(dp2, dp2 + n, inf) - dp2;39             }40         }41         //cout << ans << endl;42         for(int i = 1; i <= n; ++i) {43             int pos = lower_bound(dp1, dp1 + n, a[i]) - dp1;44             x[i] = pos + 1;45             dp1[pos] = a[i];46             if(i == n - m) {47                 ans = max(int(lower_bound(dp1, dp1 + n, inf) - dp1), ans);48                 break;49             }50         }51         //cout << ans << endl;52         printf("Case #%d: ", ca);53         dp1[0] = inf;54         for(int i = 1; i <= n; ++i) {55             dp1[i] = inf;56         }57         for(int i = m + 1; i <= n; ++i) {58             int pos = lower_bound(dp1, dp1 + n, a[i] - 1) - dp1; //求滑窗左边刚好小于滑窗右边第一个数的LIS59             ans = max(ans, y[i] + (a[i] - 1 == a[pos] ? pos + 1 : pos));60             *lower_bound(dp1, dp1 + n, a[i - m]) = a[i - m];61         }62         printf("%d\n", ans);63     }64     return 0;65 }