2017ccpc杭州 K. Master of Sequence（HDU - 6274 向下取整拆分 + 二分）

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

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

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

原式子转化为了

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

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

#include<bits/stdc++.h>
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 ac
ll 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 ac
ll 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 ac
ll 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;
}

//= ac
ll 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;
}