如果答案在某个碎片内部，那么直接悬线法解决，时间复杂度$O(n\sum)$。

 

如果$n$比较大，那么$\sum$比较小。

求出每个点向上能延伸的长度，枚举每个点向上这条线段作为短板。

算出完全可选的碎片的长度之和以及不能完全选，左边右边最大次大延伸距离，更新答案。

时间复杂度$O(n\sum^2)$。

 

如果$n$比较小，那么暴力枚举上下边界，计算答案方法同上。

时间复杂度$O(n^2\sum)$。

 

总时间复杂度$O(n\sum\sqrt{n\sum})$。

 

#include
     
      const int N=100010,M=320;int T,num,n,m,i,j,k,x,cnt,FL0,GL,FL1,FR0,GR,FR1,ans;inline void up(int&f0,int&g0,int&f1,int x,int y){  if(x>f0){f1=f0,f0=x,g0=y;return;}  if(x>f1)f1=x;}inline void uans(int x){if(ans
      
       f[j])f[j]=GL;    }else w[j]=0,f[j]=1,g[j]=m,GL=j+1;    for(GR=j=m;j;j--)if(!a[i][j]){      if(GR
       
        x-1)f[k]=x-1;        for(x=en[k];x>=st[k];x--)if(a[j][x])break;        if(g[k]
        
         f[j])f[j]=GL;    }else w[j]=0,f[j]=1,g[j]=m,GL=j+1;    for(GR=j=m;j;j--)if(!a[i][j]){      if(GR
         
          =st[k];x--)if(w[x]