lovelive好评
比赛时只拿到了60pts，还是自己太菜了
这题没有修改操作，我们像P3674一样考虑bitset
要求首项小于b且公差为b的等差数列的最大长度
把原序列分成n/b段，每一位表示是否存在
把所有的一个一个&起来就珂以判断答案了
但是，我们发现当b很小的时候，复杂度就能被卡成(O(n^2))
像P5071一样考虑当b较小时，单独处理
当b值一样时我们珂以用莫队暴力解决（细节详见代码）
这样就珂以过这题了
#include <bits/stdc++.h>
#define N 200005
#define getchar nc
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
register int x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
inline void write(register int x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[20];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
struct query{
int l,r,b,id,bl;
};
bool operator < (const query &a,const query &b){
return a.bl!=b.bl?a.l<b.l:((a.bl&1)?a.r<b.r:a.r>b.r);
}
vector <query> q[N];
int n,m,a[N],blocksize,b[N],t,ans[N],lim,maxx;
int mex[205],cnt[N];
inline void ins(register int x)
{
++cnt[a[x]];
while(cnt[mex[b[x]]*t+b[x]])
++mex[b[x]];
}
inline void rem(register int x)
{
if(--cnt[a[x]]==0)
mex[b[x]]=min(mex[b[x]],a[x]/t);
}
unsigned long long bit[N],f[N];
inline void add(register int x)
{
if(++cnt[a[x]]==1)
bit[a[x]>>6]^=1ull<<(a[x]&63);
}
inline void del(register int x)
{
if(--cnt[a[x]]==0)
bit[a[x]>>6]^=1ull<<(a[x]&63);
}
inline unsigned long long getbit(register int x,register int y)
{
int l=x>>6,r=y>>6,s=x&63,t=y&63;
if(l==r)
return (bit[l]&((1ull<<s)-1^(2ull<<t)-1))>>s;
return bit[l]>>s|(bit[r]&(2ull<<t)-1)<<(64-s);
}
int main()
{
n=read();
for(register int i=1;i<=n;++i)
a[i]=read(),maxx=max(maxx,a[i]);
m=read();
for(register int i=1;i<=m;++i)
{
int l=read(),r=read(),qb=read();
q[qb<=64?qb:0].push_back((query){l,r,qb,i,0});
}
for(t=0;t<=64;++t)
{
if(q[t].empty())
continue;
blocksize=max(1.0,sqrt(1ll*n*n/(int)q[t].size()));
for(register int i=0;i<(int)q[t].size();++i)
q[t][i].bl=(q[t][i].l-1)/blocksize+1;
sort(q[t].begin(),q[t].end());
if(t)
{
for(register int i=1;i<=n;++i)
b[i]=a[i]%t;
int l=1,r=0;
for(register int i=0;i<(int)q[t].size();++i)
{
int id=q[t][i].id,ll=q[t][i].l,rr=q[t][i].r;
while(ll<l)
ins(--l);
while(rr>r)
ins(++r);
while(ll>l)
rem(l++);
while(rr<r)
rem(r--);
for(register int j=0;j<t;++j)
ans[id]=max(ans[id],mex[j]);
}
memset(mex,0,sizeof(mex));
for(register int i=l;i<=r;++i)
cnt[a[i]]=0;
}
else
{
int l=1,r=0;
for(register int i=0;i<(int)q[t].size();++i)
{
int ll=q[t][i].l,rr=q[t][i].r,qb=q[t][i].b-1;
lim=qb>>6;
while(ll<l)
add(--l);
while(rr>r)
add(++r);
while(ll>l)
del(l++);
while(rr<r)
del(r--);
bool flag=true;
for(register int j=0;j<=lim;++j)
f[j]=(1ull<<64)-1;
for(register int j=0,s=0;;++j)
{
for(register int k=0;k<lim&&s<=maxx;++k)
{
f[k]&=getbit(s,s+63);
s+=64;
flag&=!f[k];
}
f[lim]&=getbit(s,s+(qb&63));
s+=(qb&63)+1;
flag&=!f[lim];
if(flag)
{
ans[q[t][i].id]=j;
break;
}
flag=true;
}
}
for(register int i=l;i<=r;++i)
cnt[a[i]]=0;
}
}
for(register int i=1;i<=m;++i)
write(ans[i]),puts("");
return 0;
}