【数字_ID】HDU6274 Master of Sequence（二分+树状数组+预处理）

程序员文章站 2022-06-21 17:43:07

...

题目

转载请注明地址哦
题意很简单，就是让你算最小的t，使得S(t)>=k,或者更新a/b数组
17杭州CCPC的题，感觉还是挺好的一道题，优化过程非常循序渐进，也不是特别难，但需要耐心和思考
简单说一下这道题的优化过程

1

题意很好懂，先看能不能暴力，发现不行，每次算 $S (t)$ 都要 $n$ 次，从小到大枚举t又有可能要枚举 $1 e 12 + 1 e 9$ 次，显然会T

2

经过观察发现 $S (t)$ 单调，想到二分，枚举 $t$ 大概只需要40多次，但每次算S(t)需要跑n便，复杂度 $O (n l o g n)$ ，会T，继续优化

3

看样例数据发现，a的范围1~1000，将S(t)转换成和a有关的式子然后跑1000的循环仿佛可行
设 $t = p a + q, b = m a + n$ ,则 $S (t) = t / a_{1} + b_{1} / a_{1} + (q_{1} < n_{1}) ? (- 1) : 0 + t / a_{2} + b_{2} / a_{2} + (q_{2} < n_{2}) ? (- 1) : 0 + t / a_{3} + b_{3} / a_{3} + (q_{3} < n_{3}) ? (- 1) : 0 + . . . + t / a_{n} + b_{n} / a_{n} + (q_{n} < n_{n}) ? (- 1) : 0$
这里的”/”是整除
对于 $b_{1} / a_{1} + b_{2} / a_{2} + . . . + b_{n} / a_{n}$ ，可在输入时算好，对于更新，只需要减去原来的值，在加上新的 $b_{i} ‘ / a_{i}^{'}$ 即可
因为a的范围小于1000，所以可以用1000的数组统计每个值出现的次数，从1到1000跑一遍可以算出 $t / a_{1} + t / a_{2} + . . . + t / a_{n}$

4

开始考虑余数问题，因为余数的不同情况也会对答案产生贡献，所以需要记录，当 $a = a_{i}$ 是，大于 $t % a_{i}$ 的个数
对每个a，记录余数分部情况，统计总个数，复杂度 $O (1000 * 1000)$ ，会T

5

统计前缀个数，可以用树状数组维护，1000个一维的树状数组
查询总复杂度 $O (40 * 1000 * l o g 1000)$

代码

# include <iostream>
# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <math.h>
# include <queue>
# include <string>
# include <vector>
# include <set>
# include <map>
# define INF 0x3f3f3f3f
# define Inf 0x7f7f7f7f
# define clr0(x) memset(x,0,sizeof(x))
# define clr1(x) memset(x,INF,sizeof(x))
# define clrf(x) memset(x,-1,sizeof(x))
# define rep(i,a) for(int i = 0;i<(a);i++)
# define repf(i,a,b) for(int i = (a);i<=(b);i++)
# define repu(i,a,b) for(int i = (a);i<(b);i++)
# define repd(i,a,b) for(int i = (a);i>=(b);i--)
# define lowbit(x) ((x)&(-x))
# define ww(a) while(a)
# define sc(x) scanf("%d",&(x))
# define sl(x) scanf("%lld",&(x)
# define pc(x) printf("%d\n",(x));
# define pl(x) printf("%lld\n",(x));
# define scf scanf
# define prf printf
# define wT() int T;scanf("%d",&T);while(T--)
# define wt() int T;scanf("%d",&T);for(int tt = 1;tt<=T;tt++)
# define lson(x) (x)<<1
# define rson(x) (x)<<1|1
# define ll long long
# define fuckio ios::sync_with_stdio(false);
# define fuck cout<<"fuck:"<<__LINE__<<endl;
# define maxn 200020

using namespace std;

ll A[1020][1020];//1020个一维树状数组
ll num[1020];
ll aa[100020];
ll bb[100020];
ll z;
int n,m;
int add(int x,int y,ll val)
{
    while(y<=1000){
        A[x][y] += val;
        y += lowbit(y);
    }
}

ll sum(int x,int y)
{
    ll ret = 0;
    while(y){
        ret += A[x][y];
        y -= lowbit(y);
    }  
    return ret;
}

ll funcS(ll t)
{
    ll ret = 0;
    ll yu;
    repf(a,1,1000){
        //cout<<a<<endl;
        ret += num[a]*(t/a);
        yu = t%a+1;
        int nn = sum(a,1000)-sum(a,yu);//余数大的个数，要减1*nn
        ret -= nn;
    }
    return ret;
}
int tmp;
int tmpx,tmpy;
int main()
{
    fuckio
    wT(){
        clr0(A);
        clr0(num);
        ll z = 0;
        scanf("%d%d",&n,&m);
        repf(i,1,n){
            sc(aa[i]);num[aa[i]]++;    
        }
        repf(i,1,n){
            sc(bb[i]);z += bb[i]/aa[i];
            add(aa[i],(bb[i]%aa[i]+1),1);
        }
        ww(m--){
            sc(tmp);
            if(tmp == 1){
                sc(tmpx);sc(tmpy);
                num[aa[tmpx]]--;
                add(aa[tmpx],(bb[tmpx]%aa[tmpx]+1),-1);
                z -= bb[tmpx]/aa[tmpx];
                aa[tmpx] = tmpy;
                z += bb[tmpx]/aa[tmpx];
                add(aa[tmpx],(bb[tmpx]%aa[tmpx]+1),1);
                num[aa[tmpx]]++;

            }
            else if(tmp == 2){
                sc(tmpx);sc(tmpy);
                add(aa[tmpx],(bb[tmpx]%aa[tmpx]+1),-1);
                z -= bb[tmpx]/aa[tmpx];
                bb[tmpx] = tmpy;
                z += bb[tmpx]/aa[tmpx];
                add(aa[tmpx],(bb[tmpx]%aa[tmpx]+1),1);
            }
            else if(tmp == 3){
                ll k;
                scanf("%lld",&k);
                k += z;
                ll high = 1e11;
                ll low = 0;
                ll mid;
                // repf(i,1,3000){
                //     if(funcS(i)>=tmpx){cout<<i<<endl;break;}
                // }
                ww(low<=high){
                    mid = (low+high)/2;
                    //cout<<mid<<endl;
                    if(funcS(mid)>=k){
                        high = mid-1;
                    }
                    else{
                        low = mid+1;
                    }
                }
                prf("%lld\n",high+1);
            }
        }

    }
}