本文共 2892 字，大约阅读时间需要 9 分钟。

 题意：浅显易懂不需要解释

思路：令 ，，原式子可以化简为 ，即 

当 时，第 i 项的值为 ，否则为

原式子转化为了

所以预处理 ，用二维数组 表示所有 时b[i] % a[i] >= y 的数目，二分 t 即可

（用了4种二分来练练手，都能ac）

#include
   
    using namespace std;typedef long long ll;const ll mod = 998244353;const double eps = 1e-11;const ll N = 1e5 + 10;ll a[N], b[N];///num[x][y]表示对于所有 a[i]==x 时的 b[i]%a[i] 余数大于等于y的数目ll num[1005][1005];bool check(ll mid, ll x) {    ll res = 0;    for(ll i = 1; i <= 1000; ++i) {        res += mid / i * num[i][0];        res -= num[i][mid % i + 1];    }    if(x <= res) return 1;    else return 0;}///上界不要到1e18//1 acll lower_b1(ll x) {    ll l = 1, r = 1e14, mid;    while(l < r) {        mid = (l + r) >> 1;        if(check(mid, x))            r = mid;        else            l = mid + 1;    }    return l;}//2 acll lower_b2(ll x) {    ll l = 1, r = 1e14;    while(l < r) {        ll mid = (l + r + 1) >> 1;        if(check(mid, x)) r = mid - 1;        else l = mid;    }    return l + 1;}//3 acll lower_b3(ll x) {    ll l = 0, r = 1e14;    while(l + 1 < r) {        ll mid = (l + r) >> 1;        if(check(mid, x)) r = mid;        else l = mid;    }    return l + 1;}//= acll lower_b4(ll x) {    ll l = 1, r = 1e14;    while(l <= r) {        ll mid = (l + r) >> 1;        if(!check(mid, x)) l = mid + 1;        else r = mid - 1;    }    return l;}int main() {    ll t, n, m, x, y, k, op;    scanf("%lld", &t);    while(t--) {        ll res = 0;        for(ll i = 0; i <= 1000 * 1ll; ++i)            for(ll j = 0; j < i; ++j)                num[i][j] = 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]);            res += b[i] / a[i];            num[a[i]][b[i] % a[i]]++;        }        for(ll i = 1; i <= 1000; ++i)            for(ll j = i - 1; j >= 0; --j)                num[i][j] += num[i][j + 1];        while(m--){            scanf("%lld", &op);            if(op == 1) {                scanf("%lld%lld", &x, &y);                for(ll i = b[x] % a[x]; i >= 0; --i)                    num[a[x]][i]--;                for(ll i = b[x] % y; i >= 0; --i)                    num[y][i]++;                res -= b[x] / a[x];                res += b[x] / y;                a[x] = y;            }            else if(op == 2) {                scanf("%lld%lld", &x, &y);                for(ll i = b[x] % a[x]; i >= 0; --i)                    num[a[x]][i]--;                for(ll i = y % a[x]; i >= 0; --i)                    num[a[x]][i]++;                res -= b[x] / a[x];                res += y / a[x];                b[x] = y;            }            else {                scanf("%lld", &k);                printf("%lld\n", lower_b1(res + k));//                printf("%lld\n", lower_b2(res + k));//                printf("%lld\n", lower_b3(res + k));//                printf("%lld\n", lower_b4(res + k));            }        }    }    return 0;}