HUST F - ZVINK’s garden

F The trees of HUST

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Description

As we all know that there are so many trees in HUST, so it is usually called the forest university. They were planted by teachers and students of HUST led by the president Zhu Jiusi.Though the weather of Wuhan in summer is very hot, the temperature of HUST is lower than outside. One day,Lily were thinking a problem, image that all trees is in a line,the height of trees is different,she want to know that if she ignore some contiguous trees(these trees have to be consecutive) what the numbers is in the longest increasing sequence of consecutive trees. For example, if the heights of trees were, respectively, 5, 3, 4, 9, 2, 8, 6, 7, 1, then by demolishing trees of heights 9, 2, and 8, the longest increasing sequence of consecutive trees is 3, 4, 6, 7.

Input

The input contains several test cases. The first line of the input contains a positive integer T≤25, denoting the number of test cases. Then T test cases follow, each conforming to the format described below. The input instance consists of two lines. The first one contains one positive integer n≤2*10⁵ denoting the number of trees. The second line contains n positive integers not larger than 10⁹ separated by single spaces being the heights of the trees.

Output

For each test case print the test case number as “Case #C: H” in one line where C is the test case number, where H is the length of a longest increasing sequence of consecutive trees, achievable by demolishing some consecutive trees or no trees at all.

Sample Input

2
9
5 3 4 9 2 8 6 7 1
7
1 2 3 10 4 5 6

Sample Output

Case #1: 4
Case #2: 6

Source Wzb

大意：找一个最长字串，中间只允许一个中断块。

思路：从前找最长连续子串，然后再从后找最长连续字串，枚举位置i 考虑从前后拼接出最长字串。数据大小2*10⁵ 因此查询的时候需要二分。用 f[i]，g[i]分别表示从前和从后面到位置i 的最长字串的长度。有f[i] = f[i-1] +1 当 a[i]>a[i-1] .否则 f[i]=1;

同理有g[i];

枚举位置 i ，我们需要找到从1到i-1 中最大值满足小于a[i]，且长度最长的串。首先想到的是线段树，然后加了个条件查询表示不会。

此时可以维护一个数组b[i],表示此时长度为 i 的连续上升段(从f[i]中找) 的最大值(i表示值)(即每段最后的值)的最小值。因为是动态构造，所以b[i]的值不会取到i以后的位置。那么此时让b[i]中的i 尽量大(长度尽量大) 但是b[i] 满足小于 a[i]; 那么要二分出这个结果首先 b[i] 得满足单调递增的特性。仔细想想这个特性是满足的，因为在同一个串中，长度为 i 的最长的位置比长度为 i-1的位置的数字要大。然后各自取最小值仍然满足这个条件。然后就可以二分logn的查询出来。整个算法复杂度在 nlogn。

对着代码虽然能够分析出来。但是感觉这个根本自己就不好想啊。。。光证明结论是对的就搞了半天。跟上次的题一样，注意b[i]的构造思路。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=200010;

int n,a[N],f[N],g[N],b[N];

int l,r,R0,ans;

int main() {
  int T，Case;
  scanf("%d",&T);
  while(T--) {
      scanf("%d",&n);
      for(int i=0;i<n;i++)
          scanf("%d",&a[i]);
      
      f[0]=1;
      for(int i=1;i<n;i++)
          if(a[i]>a[i-1])f[i]=f[i-1]+1;
          else f[i]=1;
          
      g[n-1]=1;
      for(int i=n-2;i>=0;i--)
          if(a[i]<a[i+1])g[i]=g[i+1]+1;
          else g[i]=1;
      
      memset(b,0x3f,sizeof(b));
      ans=R0=0;
      for(int i=0;i<n;i++) {
          l=0;
          r=R0;
          while(l<r) {
              int mid=(l+r+1)>>1;
              if(a[i]>b[mid])l=mid;
              else r=mid-1;
          }
          R0=max(R0,f[i]);
          b[f[i]]=min(b[f[i]],a[i]);
          ans=max(ans,l+g[i]);
      }
      
      printf("Case #%d: %d\n",++Case,ans);
  }
  return 0;
}