题目传送门：http://ifrog.cc/acm/problem/1112

神奇的倍增二分，长见识了，在此做个记录，分享给大家。

懒得写题解了，直接转YJQ的：http://ifrog.cc/acm/solution/18

另外，这个复杂度的证明我不是很懂，只会自己瞎脑补的不严谨的证明，如果哪位神犇会，还请教教我qwq。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4  5 using namespace std; 6 typedef long long ll; 7 const int MAXN = 300010; 8  9 int n;10 ll m, a[MAXN], v[MAXN];11 int ans[MAXN] = {
   0};12 13 ll tmp[MAXN];14 bool check( int begin, int end ) { // 区间混乱度大于m返回true15     for( int i = begin; i < end; ++i ) tmp[i] = a[i];16     sort(tmp+begin, tmp+end);17     ll sum = 0;18     for( int i = begin; i < end; ++i )19         sum += tmp[i] * v[i-begin];20     return sum > m;21 }22 23 int main() {24     scanf( "%d%lld", &n, &m );25     for( int i = 0; i < n; ++i ) scanf( "%lld", a+i );26     for( int i = 0; i < n; ++i ) scanf( "%lld", v+i );27     for( int i = 0; i < n; ) {28         int k;29         for( k = 1; i+k <= n; k <<= 1 ) // 倍增，左闭右开区间30             if( check(i,i+k) ) break;31         k = min(k, n-i);32         int low = i+(k>>1), high = i+k;33         while( low < high ) { // 二分34             int mid = (low+high)>>1;35             if( check(i,mid) ) high = mid;36             else low = mid+1;37         }38         if( check(i,low) ) ans[low-1] = 1;39         i = low;40         // printf( "low = %d\n", low );41     }42     for( int i = 0; i < n; ++i ) {43         if(i) ans[i] += ans[i-1], putchar(' ');44         printf( "%d", ans[i] );45     }46     puts("");47     return 0;48 }