1 #include
     
       2 #include
      
        3 int a[500005],b[500005],d[500005]; 4 void sort(int l,int r) 5 { 6     int i=l,j=r,x=a[(i+j)/2],y; 7     while (i<=j) 8     { 9         while (a[i]
       
        d[maxlen])41             {42                 maxlen++;43                 d[maxlen]=b[i];44             }45             else doit(1,maxlen,b[i]);46         }47         t++;48         printf("Case %d:\n",t);49         if (maxlen==1) printf("My king, at most 1 road can be built.\n\n");50         else printf("My king, at most %d roads can be built.\n\n",maxlen);51     }52 }
       
      
     

 

 

<补年轻时的坑>：二分不用手写，最长上升是lower_bound，最长不下降是upper_bound