题目
分析
对于$$sum_{i=1}^{n}lfloordfrac{T-B_i}{A_i}
floor$$
我们考虑拆开处理，得到
[sum_{i=1}^{n}(lfloordfrac{T}{A_i}
floor-lfloordfrac{B_i}{A_i}
floor)-[T\%A_i<B_i\%A_i]
]
因为(A_i<=1000)，那么我们可以
对于每个模数(mo=A_i)
设S[mo][j]，记录B数组中模mo后为j的个数，并且对于S[mo]求一个前缀和。
对于修改操作，直接在A数组或B数组上修改，并且修改S数组以及O(N)更新前缀和。
而对于查询操作，二分T，判断是否合法。
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
const int maxlongint=2147483647;
const int mo=1e9;
const int N=200005;
const int M=1000;
using namespace std;
int a[N],b[N],n,m,T,c[M+100][M+100],sum[M+100][M+100];
long long num;
void read(int &n)
{
char ch=' ';int q=0,w=1;
for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
if(ch=='-')w=-1,ch=getchar();
for(;ch>='0' && ch<='9';ch=getchar())q=(q<<1)+(q<<3)+ch-'0';n=q*w;
}
int prt[20];
void write(long long x)
{
if(x<0) putchar('-'),x=-x;
for(;x;x/=10) prt[++prt[0]]=x%10;
if(!prt[0]) prt[++prt[0]]=0;
for (;prt[0];putchar('0'+prt[prt[0]--]));
}
void cha(int x)
{
sum[x][0]=c[x][0];
for(int j=1;j<=M;j++) sum[x][j]=sum[x][j-1]+c[x][j];
}
bool check(int k,int t)
{
long long su=-num;
for(int i=1;i<=M && su<k;i++) su=su+1ll*sum[i][M]*(t/i)-1ll*(sum[i][M]-sum[i][t%i]);
return su>=k;
}
int main()
{
read(T);
for(;T--;)
{
read(n),read(m);
memset(c,0,sizeof(c));
memset(sum,0,sizeof(sum));
num=0;
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<=n;i++)
{
read(b[i]);
num+=1ll*(b[i]/a[i]);
c[a[i]][b[i]%a[i]]++;
}
for(int i=1;i<=M;i++) cha(i);
for(int i=1,x,y,t;i<=m;i++)
{
read(t),read(x),t--;
if(t<2)
{
read(y);
c[a[x]][b[x]%a[x]]--;
cha(a[x]);
num-=1ll*(b[x]/a[x]);
if(!t) a[x]=y;
else b[x]=y;
num+=1ll*(b[x]/a[x]);
c[a[x]][b[x]%a[x]]++;
cha(a[x]);
}
else
{
long long l=0,r=mo;
while(l<r)
{
long long mid=(l+r)>>1;
if(check(x,mid)) r=mid;
else l=mid+1;
}
write(l),putchar('
');
}
}
}
}