P5313 WBLT
题面
题解
显然可以莫队，端点移动 \(O(n\sqrt n)\)。
首先，对于 \(b\) 较大的情形，考虑莫队配合 \(\mathrm{bitset}\)，每次从中截取一段进行与运算直到全为 \(0\)，复杂度 \(O(\frac{n^2}{w}+\frac{n^2}{b})\)。
对于 \(b\) 较小的情形比较难处理。
我们可以枚举所有可能的 \(b\)，对于每个 \(b\) 单独跑一个莫队，查答案就是枚举 \(a\)，这里用分块实现单点修改和查询第一个 \(0\)，复杂度 \(O(n\sqrt{nb})\)。
取 \(b\sim w\)，复杂度 \(O(n\sqrt{nw}+\frac {n^2}w)\)，可以通过。
Code
#include<bits/stdc++.h>
#pragma optimize("Ofast")
#pragma optimize("unroll-loops")
#pragma optimize("inline")
#pragma optimize("-ffast-math")
#pragma optimize("-fstrict-aliasing")
#pragma optimize("-funsafe-loop-optimizations")
using namespace std;
struct Magic {unsigned int m; unsigned int s; };
Magic compute_magic(unsigned int d){
if(d==1){
return {1,0};
}
unsigned long long M=(1ull<<32)/d;
if((1ull<<32)%d!=0){
++M;
}
return {M,32};
}
const int lim=30;
struct bs{
vector<unsigned long long>d;
int len;
int operator[](const int x)const{
return (d[x>>6]>>(x&63))&1;
}
inline void set1(int x){
d[x>>6]|=1ull<<(x&63);
}
inline void set0(int x){
d[x>>6]&=~(1ull<<(x&63));
}
bs(){
len=0; d.clear();
}
bs(int le){
len=le; d.clear(); d.resize(le+63>>6);
}
inline void set(){
for(int i=0;i<d.size()-1;i++) d[i]=-1ull;
d[d.size()-1]=(1ull<<(len&63))-1;
if(!(len&63)) d[d.size()-1]=-1ull;
}
inline void reset(){
for(int i=0;i<d.size();i++) d[i]=0ull;
}
bool operator&=(const bs &c){
bool flag=1;
for(int i=0;i<d.size();i++){
d[i]&=c.d[i]; if(d[i]) flag=0;
}return flag;
}
bool empty(){
for(int i=0;i<d.size();i++) if(d[i]) return 0; return 1;
}
bool substr(int l,int r,bs &my){
if((l>>6)==(r>>6)){
my.d[0]&=(d[l>>6]>>(l&63))&((r&63)==63?-1ull:((1ull<<((r&63)+1))-1));
return !my.d[0];
}
int pos=l&63;
int fin=0;
bool flag=1;
if(pos==0){
for(int i=(l>>6);i<=(r>>6);i++){
if(fin==my.d.size()){
break;
}
my.d[fin]&=(d[i]>>pos);
if(my.d[fin]) flag=0;
fin++;
}
}else{
for(int i=(l>>6);i<=(r>>6);i++){
if(fin==my.d.size()){
break;
}
if(i+1<d.size()) my.d[fin]&=(d[i]>>pos)|(d[i+1]<<(64-pos));
else my.d[fin]&=(d[i]>>pos);
if(my.d[fin]) flag=0;
fin++;
}
}
return flag;
}
};
int n,q;
int a[100005];
struct qry{
int l,r,b,id,ans;
};
qry s[100005];
struct ds{
int b=120;
bool a[100005];
int sum[1005];
unsigned long long hh;
int ss;
void init(int n){
memset(sum,0,sizeof(sum)); memset(a,0,n+2);
}
void update(int u,int v){
if(a[u]==0&&v==1) sum[(hh*u)>>ss]++;
else if(a[u]==1&&v==0) sum[(hh*u)>>ss]--;
a[u]=v;
}
int mex(){
for(int i=0;;i++){
if(sum[i]!=b){
for(int j=i*b;j<(i+1)*b;j++){
if(!a[j]) return j;
}
}
}
}
};
bs c(200005); int nv[100005];
inline void add1(int v){
nv[v]++; c.set1(v);
}
inline void del1(int v){
nv[v]--; if(!nv[v]) c.set0(v);
}
// /*
int CNT;
inline int getans1(int d){
bs x(d); x.set();
for(int i=0;;i++){
if(i*d>100000) return i;
if(c.substr(i*d,i*d+d-1,x)) return i;
}
return 0;
}
// */
ds w[lim+5];
int Div=400;
inline bool cmp1(qry x,qry y){
if(x.l/Div!=y.l/Div) return x.l<y.l; return x.r<y.r;
}
inline bool cmp2(qry x,qry y){
return x.id<y.id;
}
unsigned long long hh;
int ss;
inline void add2(int v,int k){
register int cc=(hh*v)>>ss;
nv[v]++; w[v-cc*k].update(cc,1);
}
inline void del2(int v,int k){
register int cc=(hh*v)>>ss;
nv[v]--; if(!nv[v]) w[v-cc*k].update(cc,0);
}
inline int getans2(int k){
int res=0;
for(int i=0;i<k;i++) res=max(res,w[i].mex());
return res;
}
int tg[lim+5];
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n; for(int i=1;i<=n;i++) cin>>a[i];
cin>>q; for(int i=1;i<=q;i++) {
cin>>s[i].l>>s[i].r>>s[i].b; s[i].id=i;
if(s[i].b<=lim) tg[s[i].b]++;
}
sort(s+1,s+1+q,cmp1);
int nl=1,nr=0;
for(int i=1;i<=q;i++){
if(s[i].b<=lim) continue;
while(nl>s[i].l) add1(a[--nl]);
while(nr<s[i].r) add1(a[++nr]);
while(nl<s[i].l) del1(a[nl++]);
while(nr>s[i].r) del1(a[nr--]);
s[i].ans=getans1(s[i].b);
}
for(int k=1;k<=lim;k++){
if(tg[k]==0) continue;
Magic ttmp=compute_magic(k); hh=ttmp.m; ss=ttmp.s;
Div=max(1.1,n/sqrt(tg[k]-0.1)*1.6);
int dd=q;
for(int i=1;i<=tg[k];i++){
if(s[i].b!=k){
while(s[dd].b!=k) dd--;
swap(s[i],s[dd]);
}
}
sort(s+1,s+1+tg[k],cmp1);
nl=1,nr=0;
int tmp=sqrt((n+1)/k); Magic ccf=compute_magic(tmp);
for(int h=0;h<k;h++){
w[h].init(n/k); w[h].b=tmp; w[h].hh=ccf.m; w[h].ss=ccf.s;
}
memset(nv,0,sizeof(nv));
for(int i=1;i<=tg[k];i++){
while(nl>s[i].l) add2(a[--nl],k);
while(nr<s[i].r) add2(a[++nr],k);
while(nl<s[i].l) del2(a[nl++],k);
while(nr>s[i].r) del2(a[nr--],k);
s[i].ans=getans2(k);
}
}
sort(s+1,s+1+q,cmp2);
for(int i=1;i<=q;i++) cout<<s[i].ans<<'\n';
return 0;
}