bzoj4320 homework 题解

题面链接：https://www.lydsy.com/JudgeOnline/problem.php?id=4320

令M=sqrt(mx)，把询问的Y按<M和>M 分成两种不同的处理方式。

1、对于>M的Y，我们发现它的倍数不超过M个，于是可以枚举倍数，找到往后第一个已经被加入集合的值，用差值更新答案。

这个东西我们可以离线，倒序枚举询问，然后用并查集维护。

单次查询O(M),更新O(1).

2、对于<M的Y，倍数肯定是>M，不过这样的Y也就M个，可以直接拿数组存，g[i]表示目前%i最小为多少（即答案），更新的时候直接遍历M个位置取min即可。

单次查询O(1),更新O(M).

所以总时间复杂度为O(n*sqrt(n))的。

#include<bits/stdc++.h>

using namespace std;

const int N = 300005;

#define rep(i,a,b) for(register int i=(a);i<=(b);++i)

#define dwn(i,a,b) for(register int i=(a);i>=(b);--i)

typedef long long ll;

int n,X[N],Y[N],ans[N],fa[N],g[N],kua,mx,mn;

bool vis[N];

char s[2];

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

int main(){

    memset(ans,-1,sizeof(ans));

    scanf("%d",&n);

    rep(i,1,n){

        scanf("%s%d",s,&Y[i]);

        if(s[0]=='A')X[i]=1,vis[Y[i]]=1;

        else X[i]=2;

        mx=max(mx,Y[i]);

    }

    kua=sqrt(mx)+1;

    rep(i,0,mx+1)fa[i]=i;

    dwn(i,mx,0){

        if(vis[i])continue;

        fa[find(i)]=find(i+1);

    }

    memset(g,0x3f,sizeof(g));

    rep(i,1,n){

        if(X[i]==1){

            rep(j,1,kua){

                g[j]=min(g[j],Y[i]%j);

            }

        }

        else if(Y[i]<=kua)ans[i]=g[Y[i]];

    }

    dwn(i,n,1){

        if(X[i]==1){

            fa[find(Y[i])]=find(Y[i]+1);

        }

        else if(Y[i]>kua){

            mn=1e9;

            for(int j=0;j<=mx;j+=Y[i]){

                if(find(j)>mx)continue;

                mn=min(mn,find(j)-j);

            }

            ans[i]=mn;

        }

    }

    rep(i,1,n)if(~ans[i])printf("%d\n",ans[i]);

    return 0;

}

巴特西

bzoj4320 homework 题解

最新文章

热门文章