HDU 6274 Master of Sequence (暴力+下整除)

题意

两个1e5的数组a,b，定义\(S(t)=\left \lfloor \frac{t-b_i}{a_i} \right \rfloor\)，有三个操作
1 x y：将\(a[x]\)变为\(y\)
2 x y：将\(b[x]\)变为\(y\)
3 x：求使得\(S(t)\geq k\)的最小\(k\)
其中\(a_i\leq 1000\),\(b_i,k\leq 1e9\)

思路

这题主要突破口在于\(a_i\leq 1000\)
我们先从下整除下手，
\(\left \lfloor \frac{t-b_i}{a_i} \right \rfloor=\left \lfloor \frac{k_1a_i+c_1-k_2a_i-c_2}{a_i} \right \rfloor=k_1-k_2+\left \lfloor \frac{c_1-c_2}{a_i} \right \rfloor\)
其中
\(c_1=t\bmod a_i\)
\(c_2=b_i \bmod a_i\)
\(c_1=t/ a_i\)
\(c_1=b_i/ a_i\)
\(\left \lfloor \frac{c_1-c_2}{a_i} \right \rfloor=\left\{\begin{matrix} -1,c_1<c_2\\ 0,c_1\geq c_2 \end{matrix}\right.\)
那么
\(S(t)=ret+\sum_{i=1}^{1000}(\frac{t}{i}cnt[i]-f[i][t\bmod i+1])\)
其中
\(f[x][y]\)表示\(a_i=x\)时，\(y \leq c_2 \leq 1000\)的个数
\(cnt[x]\)表示\(a_i=x\)的个数，即\(f[x][0]\)
\(ret\)表示所有数\(k_2\)的和
这题就做完了。。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<map>
#include<functional>

#define fst first
#define sc second
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lc root<<1
#define rc root<<1|1
#define lowbit(x) ((x)&(-x))

using namespace std;

typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
typedef pair<ll,ll> PLL;

const db eps = 1e-6;
const int mod = 998244353;
const int maxn = 2e6+100;
const int maxm = 2e6+100;
const int inf = 0x3f3f3f3f;
const db pi = acos(-1.0);

int n,m;
ll a[maxn],b[maxn];
ll f[1111][1111];
ll ret;
ll S(ll t){
    ll ans = 0;
    for(int i = 1; i <= 1000; i++){
        ans+=t/i*f[i][0]-f[i][t%i+1];
    }
    return ans-ret;
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; i++){
            scanf("%lld",&a[i]);
        }
        for(int i = 1; i <= n; i++){
            scanf("%lld", &b[i]);
        }
        mem(f,  0);
        ret = 0;
        for(int i = 1; i <= n; i++){
            ret+=b[i]/a[i];
            f[a[i]][b[i]%a[i]]++;
        }
        for(int i = 1; i <= 1000; i++){
            for(int j = i-1; j >= 0; j--){
                f[i][j]+=f[i][j+1];
            }
        }
        while(m--){
            int op,x;
            ll y;
            scanf("%d",&op);
            if(op<=2){
                scanf("%d %lld", &x ,&y);
                if(op==1){
                    ret-=b[x]/a[x];
                    ret+=b[x]/y;
                    for(int i = b[x]%a[x]; i >= 0; i--)f[a[x]][i]--;
                    for(int i = b[x]%y; i >= 0; i--)f[y][i]++;
                    a[x]=y;
                }
                else if(op==2){
                    ret-=b[x]/a[x];
                    ret+=y/a[x];
                    for(int i = b[x]%a[x]; i >= 0; i--)f[a[x]][i]--;
                    for(int i = y%a[x]; i >= 0; i--)f[a[x]][i]++;
                    b[x]=y;
                }
            }
            else{
                ll ans = 0;
                scanf("%lld", &y);
                ll l = 0,r = 1e13;
                while(l<=r){
                    ll mid = l+r>>1;
                    if(S(mid)>=y){
                        ans=mid;r=mid-1;
                    }
                    else l=mid+1;
                }
                printf("%lld\n",ans);
            }

        }

    }
    return 0;
}
/*
2
4 6
2 4 6 8
1 3 5 7
1 2 3
2 3 3
3 15
1 3 8
3 90
3 66
8 5
2 4 8 3 1 3 6 24
2 2 39 28 85 25 98 35
3 67
3 28
3 73
3 724
3 7775
 */