\(\color{skyblue}9-nine-\) 专场（

小阳历最水的一回。

日常RE挂分。

我这是不是风水不好？（逃）

9-nine-九次九日九重色

赛时以为是连续的...大样例模了半天没模懂...

按连续的思路打了个二分上去...还骗了30pts？(

官方题解

按照官方题解写的Code，但WA #1，不知道哪错了...

int n,a[N],b[N],posb[N],posa[N],num[N];
vector<pair<int,int> > vec;

#define fi first
#define se second

bool cmp(pair<int,int> x,pair<int,int> y){
	if(x.fi==y.fi){
		return x.se>y.se;
	}else{
		return x.fi<y.fi;
	}
}

signed main(){
	n=rd;
	for(int i=1;i<=n;i++) a[i]=rd,posa[a[i]]=i;
	for(int i=1;i<=n;i++) b[i]=rd,posb[b[i]]=i;
	int cnt=0;
	vec.psb(mkp(-1,-1));
	for(int i=1;i<=n;i++){
		for(int j=1;i*j<=n;j++){
			vec.psb(mkp(posa[i],posb[i*j]));
			++cnt;
		}
	}
	sort(vec.begin(),vec.end(),cmp);
	
	num[1]=vec[1].se;
	int len=1;
	for(int i=2;i<=cnt;i++){
		if(vec[i].se>num[len]){
			num[++len]=vec[i].se;
		}else{
			int j=lower_bound(num+1,num+1+len,vec[i].se)-num;
			num[j]=vec[i].se;
		}
	}

	printf("%lld",len);
	return Elaina;
}

9-nine-天色天歌天籁音

守磨一下就会发现实际上是让求区间众数。

赛时打分块爆内存了，不愧是我先天RE圣体。

后来发现分块复杂度超了，遂改为莫队。

int n,m,maxn,len,ans[N],cnt[N],a[N],bl[N],sum[N];
struct Q{
	int l,r,id;
}q[N];
vector<int> lsh;
bool cmp(Q x,Q y){
	if(bl[x.l]==bl[y.l]){
		if(bl[x.l]&1) return x.r<y.r;
		else return x.r>y.r;
	}else return x.l<y.l;
}

void add(int x){
	sum[++cnt[a[x]]]++;
	if(cnt[a[x]]>maxn) maxn=cnt[a[x]];
	return;
}

void del(int x){
	if(sum[cnt[a[x]]]==1&&maxn==cnt[a[x]]) maxn--;
	sum[cnt[a[x]]--]--;
	return;
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	n=rd,m=rd;
	len=sqrt(n);
	for(int i=1;i<=n;i++){
		a[i]=rd;
		lsh.psb(a[i]);
		bl[i]=(i-1)/len+1;
	}
	sort(lsh.begin(),lsh.end());
	lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(lsh.begin(),lsh.end(),a[i])-lsh.begin()-1;
	}
	
	for(int i=1;i<=m;i++){
		int l=rd,r=rd;
		q[i].l=l,q[i].r=r,q[i].id=i;
	}
	sort(q+1,q+1+m,cmp);
	
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		while(l>q[i].l) add(--l);
		while(r<q[i].r) add(++r);
		while(r>q[i].r) del(r--);
		while(l<q[i].l) del(l++);
		ans[q[i].id]=-maxn;
	}
	for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
	return Elaina;
}

9-nine-春色春恋春熙风

别催了...在改了 T^T

9-nine-雪色雪花雪余痕

既然是9-nine专场，那挂张图吧