n^2 过百万？

12345678910111213141516171819202122232425262728293031323334353637#include<iostream>
#include<cmath>
#define endl '\n'
using namespace std;
using ll=long long;
int t,n,c[1000005];
ll a[1000005],b[1000005];
ll ceil(ll a,ll b){return a/b+bool(a%b);}
bool chk(ll x){
    ll tota=0,totb=0;
    for(int i=1;i<=n;i++){
		totb+=b[i];
		if(tota<c[i]*x){
			ll p=min(totb,ceil(c[i]*x-tota,a[i]));
			tota+=p*a[i],totb-=p;
		}
		if((tota-=x)<0) return false;
    }
    return true;
}
int main(){
    cin>>t;
    while(t--){
        ll l=1,r=0,ans=0;
		cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i]; a[n+1]=0x3f3f3f3f3f3f3f3fll;
        for(int i=1;i<=n;i++) cin>>b[i],r=max(r,a[i]*b[i]);
        for(int i=1;i<=n;i++) for(int j=i+1;j<=n+1;j++) if(a[j]>=a[i]){c[i]=j-i; break;}
        while(l<=r){
            ll mid=l+r>>1;
            if(chk(mid)) ans=max(ans,mid),l=mid+1;
            else r=mid-1;
        }
        cout<<ans<<endl;
    }
    return 0;
}