题址：http://www.ifrog.cc/acm/problem/1112
小 L 有一串 QQ 个数排成一排，从左往右是 A1A1 开始一直到 AQAQ，它一直很喜欢这串数。
有一天，小 L 去高考报名了，小 J 和小 N 过来用这串数玩游戏。
一开始，小 N 手上有一个空序列，定义变量C:=0C:=0。小 J 从左往右依次把序列中的数取出，放到小 N 手上序列的最右边，如果放完之后，整个序列的混乱度超过了 MM，小 N 就会把手上的所有数全部扔掉，然后令 C:=C+1C:=C+1。
定义一个长度为 KK 序列的混乱度 S=K∑i=1Bi×ViS=∑i=1KBi×Vi，其中BiBi 表示序列中第 ii 小的数，VV 为一个给定的序列。
小 J 和小 N 想知道，加入每个数之后，CC 是多少。
INPUT第一行两个整数QQ，MM接下来一行QQ个整数， 第ii个整数表示AiAi接下来一行QQ个整数， 第ii个整数表示ViViOUTPUT一行QQ个整数， 第ii个整数表示加入第ii个数之后的CC， 相邻两个整数之间用空格隔开， 注意最后一个数后不要输出空格输出完请换行SAMPLE INPUT5 11 3 2 5 41 1 1 1 1SAMPLE OUTPUT0 1 2 3 4HINT1≤Q≤300000,0≤M≤1018,1≤Ai≤108,1≤Vi≤1041≤Q≤300000,0≤M≤1018,1≤Ai≤108,1≤Vi≤104对于所有的1≤i≤Q−1,Vi≤Vi+11≤i≤Q−1,Vi≤Vi+1题意：混乱度为当前的序列排好序后与V【】的乘积和，当混乱度大于M时，把当前序列全部扔掉，并且让c+1，输出每个数的c值是多少。思路：左端点固定，倍增找右端点的范围，二分找右端点，然后左端点移到右端点+1，重复这个过程；
比赛的时候没听说过倍增思想，一直超时。这个思想挺重要的，学到了0.0AC代码如下：
#define N 1000010
int a[N],v[N],num[N],p[N];
int n;
LL m;
int find(int x,int y)
{
LL sum=0;
int len=0;
for(int i=x;i<=y;i++)
p[len++]=a[i];
sort(p,p+len);
for(int i=0;i<len;i++)
sum+=p[i]*v[i];
if(sum>m)return 1;
else return 0;
}
int main()
{
int ans=0;
scanf("%d%lld",&n,&m);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
for(int i=0;i<n;i++)
scanf("%d",&v[i]);
for(int i=0;i<n;i++)
{
int k;
for(k=1;k<n;k*=2)if(find(i,i+k))break;
int l=i+k/2,r=i+k,mid;
while(l<r)
{
mid=(r+l)/2;
if(find(i,mid))r=mid;
else l=mid+1;
}
for(;i<=l;i++)
{
if(i==l)
{
num[i]=++ans;
break;
}
num[i]=ans;
}
}
for(int i=0;i<n;i++)
{
if(i)
printf(" ");
printf("%d",num[i]);
}
printf("\n");
}