Problem
Solution
前置技能：分块+线段树+卡常+一点小小的数学知识
考试时A的
这种题无论怎么处理总有瓶颈，套路分块，设(k)以下的插入时直接暴力预处理，查询时直接调用；(k)以上的插入时不管，查询时线段树查找每个模意义下的区间
核心代码：
if(opt[0]=='A'){
for(rg int i=1;i<=k;++i)f[i]=min(f[i],x%i);
update(1,n,1,x);
}
else
if(x<=k)printf("%d
",f[x]);
else {
int res(inf);
for(rg int i=0;i<=n;i+=x)
res=min(res,query(1,n,1,max(1,i),min(i+x-1,n))-i);
printf("%d
",res);
}
考虑到当分界线为(k)，变量为(x)时，插入复杂度为(O(k))，查询时复杂度为(O(1))或(O(frac nxlog_2n)leq O(frac nklog_2n))
如果直接采用大众分块做法（块大小为(sqrt n)），则算法瓶颈为(O(sqrt n log_2n))，总体复杂度(O(nsqrt nlog_2n))无法通过此题
考虑算法瓶颈，总体单次复杂度为(O(k+frac nklog_2n))，利用基本不等式(a+bgeq 2sqrt{ab})，得知总体单次复杂度最小为(O(2sqrt{kcdot frac nk log_2n})=O(sqrt{nlog_2n}))，而满足这个不等式取等的条件是(a=bLeftrightarrow k=frac nk log_2nLeftrightarrow k=sqrt {nlog_2n})，再考虑上取膜运算和线段树的常数因子影响，取(k=1732)时最优
注意，以上并非平均情况下的最优，而是最差情况下的最优（一般情况下(k=sqrt n)的程序甚至更快），也就是说，如果出题人看了你的程序，精心构造数据卡你，(k=1732)的程序被卡后是最快的，可以保证复杂度在(O(nsqrt {n log_2 n}))
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rg register
template <typename _Tp> inline _Tp read(_Tp&x){
char c11=getchar(),ob=0;x=0;
while(c11^'-'&&!isdigit(c11))c11=getchar();if(c11=='-')c11=getchar(),ob=1;
while(isdigit(c11))x=x*10+c11-'0',c11=getchar();if(ob)x=-x;return x;
}
const int N=301000,inf=0x7fffffff;
int f[N],s[N<<2],fc[N];
int Q,k,n=300000;
void pre(){// 1817|1732
k=1732;
for(rg int i=1;i<=k;++i)f[i]=inf;
/* fc[0]=-1;
for(rg int i=1;i<=n;++i)fc[i]=fc[i>>1]+1;
double mi=inf,tp;k=1;
for(rg int i=2;i<=n;++i)
if((tp=abs(i*i-1.0*n*fc[i]))<1.0*mi)mi=tp,k=i;*/
}
void build(int l,int r,int x){
s[x]=inf;
if(l==r)return ;
int mid(l+r>>1);
build(l,mid,x<<1);
build(mid+1,r,x<<1|1);
return ;
}
inline void update(int l,int r,int x,int ps){
if(l==r){s[x]=l;return ;}
int mid(l+r>>1);
if(ps<=mid)update(l,mid,x<<1,ps);
else update(mid+1,r,x<<1|1,ps);
s[x]=min(s[x<<1],s[x<<1|1]);return ;
}
inline int query(int l,int r,int x,int L,int R){
if(L<=l&&r<=R)return s[x];
int mid(l+r>>1),res(inf);
if(L<=mid)res=min(res,query(l,mid,x<<1,L,R));
if(mid<R)res=min(res,query(mid+1,r,x<<1|1,L,R));
return res;
}
int main(){
freopen("f.in","r",stdin);
freopen("f.out","w",stdout);
pre();read(Q);
build(1,n,1);
char opt[2];int x;
while(Q--){
scanf("%s",opt);read(x);
if(opt[0]=='A'){
for(rg int i=1;i<=k;++i)f[i]=min(f[i],x%i);
update(1,n,1,x);
}
else
if(x<=k)printf("%d
",f[x]);
else {
int res(inf);
for(rg int i=0;i<=n;i+=x)
res=min(res,query(1,n,1,max(1,i),min(i+x-1,n))-i);
printf("%d
",res);
}
}return 0;
}