Master of Sequence（数学+二分+树状数组）

题意：给两个长度为n的序列(a1,a2......,an)、(b1,b2......bn)和m个询问以及一个整数k，找出满足k <= S(t) = Σ(i=1 to n) ((t-bi) / ai)向下取整  的最小t。考虑函数的单调性此题可以二分，对于该式子可以证明 ((t-bi) / ai)向下取整的值就是 (t/ai)向下取整的值减去 (bi/ai)向下取整的值 如果 (t%ai) - (bi%ai) 的值比0小，说明还得到前面算出来的(t/ai)的值那里拿一个1来减， 所以算出来的值应该减1。 考虑a的值小于1000，用1000个树状数组维护每个(bi % ai)的前缀和，用一个大小为1000的数组nums维护每个ai出现的次数,用一个变量sum记录Σ(i=1 to n)bi/ai的和，则对于每个t，S(t)可以通过以下方式计算得到：i从for 1到1000 记录(t/i) * nums[ai]的值，这个值减去sum得到的是未经过取余处理的值，然后i 从1for到1000的过程中可以减去 (bi %ai)比(t%i)大的个数，这个数可以通过树状数组查询(getsum(t%ai))表示查找<=t%ai的数 然后用总个数nums[ai]减去它得到。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3+10;
const int maxm = 1e5+10;
int t,n,m,op;
ll x,y,k;
ll a[maxm],b[maxm];
int nums[maxn];
int lowbit(int x) {return x&(-x);}
struct tree{
    int c[maxn];
    inline void update(int x,int y){
        x++;
        for(int i=x;i<maxn;i+=lowbit(i))
        c[i] += y;
    }
    inline int getsum(int x){
           int ans = 0;x++;
           for(int i=x;i;i-=lowbit(i))
           ans += c[i];
        return ans;
    }
}node[maxn];
bool check(ll t){
    ll tmp = 0;
    for (int i = 1; i <= 1000; i++){
        tmp += (t / i) * nums[i] - (nums[i] - node[i].getsum(t % i));
        if (tmp >= k + 1000 - i) return true;
    }
    return tmp >= k;
}
int main(){
    scanf("%d",&t);
    while (t--){
        ll sum = 0;
        memset(nums, 0, sizeof nums);
        memset(node, 0, sizeof node);        
        scanf("%d%d",&n,&m);
        for (int i = 1; i <= n; i++){
            scanf("%lld",&a[i]);
            nums[a[i]]++;
        }
        for (int i = 1; i <= n; i++){
            scanf("%lld",&b[i]);
            sum += b[i] / a[i];
            node[a[i]].update(b[i]%a[i],1);
        }
        while (m--){
            scanf("%d",&op);
            if (op == 1){
                scanf("%lld%lld",&x,&y);
                nums[a[x]]--,nums[y]++;
                node[a[x]].update(b[x] % a[x], -1);
                node[y].update(b[x] % y, 1);
                sum = sum - b[x] / a[x] + b[x] / y;
                a[x] = y;
            }
            else if (op == 2){
                scanf("%lld%lld",&x,&y);
                node[a[x]].update(b[x]%a[x], -1);
                node[a[x]].update(y%a[x], 1);
                sum = sum - b[x] / a[x] + y / a[x];
                b[x] = y;
            }
            else{
                scanf("%lld",&k);
                ll l = 0, r = 1e12, ans;
                k += sum;
                while (l <= r){
                    ll mid = (l + r) >> 1;
                    if (check(mid)) {
                        ans = mid;
                        r = mid-1;
                    }
                    else l = mid + 1;
                }
                printf("%lld\n",ans);
            }
        }
    }
    return 0;
}