1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
|
#include<bits/stdc++.h> using namespace std; #define Debug(x) cout<<#x<<':'<<x<<endl #define INF 0x7fffffff typedef long long ll; typedef pair<ll,ll> P; const ll maxn=1e5+11;
ll f[1111][1111],a[maxn],b[maxn],num[1111]; ll n,m,sum;
ll lowbit(ll x){return x & -x;} void update(ll i,ll x,ll val){for(;x<=1000;f[i][x]+=val,x+=lowbit(x));}
ll getsum(ll i,ll x){ll sum=0;for(;x>=1;sum+=f[i][x],x-=lowbit(x));return sum;}
ll check(ll mid,ll k){ ll ans=0; for(ll i=1;i<=1000;i++){ ans=ans+mid/i*num[i]; ans=ans-num[i]+getsum(i,mid%i+1); } ans-=sum; if(ans>=k) return 1; else return 0; }
void solve(ll k){ ll l=0,r=1e9+11; while(l<r){ ll mid=(l+r)/2; if(check(mid,k)) r=mid; else l=mid+1; } printf("%lld\n",l); }
int main(){ ll ca;scanf("%lld",&ca); while(ca--){ memset(f,0,sizeof(f));memset(num,0,sizeof(num)); sum=0; scanf("%lld%lld",&n,&m); for(ll i=1;i<=n;i++) scanf("%lld",&a[i]); for(ll i=1;i<=n;i++){ scanf("%lld",&b[i]); sum+=b[i]/a[i]; update(a[i],b[i]%a[i]+1,1); num[a[i]]++; } for(ll i=1;i<=m;i++){ ll type;scanf("%lld",&type); if(type==1){ ll x,y;scanf("%lld%lld",&x,&y); sum-=b[x]/a[x]; sum+=b[x]/y; update(a[x],b[x]%a[x]+1,-1); num[a[x]]--; update(y,b[x]%y+1,1); num[y]++; a[x]=y; } else if(type==2){ ll x,y;scanf("%lld%lld",&x,&y); sum-=b[x]/a[x]; sum+=y/a[x]; update(a[x],b[x]%a[x]+1,-1); num[a[x]]--; update(a[x],y%a[x]+1,1); num[a[x]]++; b[x]=y; } else{ ll k;scanf("%lld",&k); solve(k); } } } return 0; }
|