专栏文章

题解：P14316 [Aboi Round 2] 礎の花冠

ddiqiuyi奶龙
P14316题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minh7xw7
此快照首次捕获于
2025/12/02 02:22
3 个月前
此快照最后确认于
2025/12/02 02:22
3 个月前
查看原文
一种可以避免查询同块区间 max⁡\max 的办法。
数据范围像是根号，所以优先考虑根号做法。（默认 n,m,ain,m,a_i 同阶）
x=0/1x=0/1 是平凡的，以下考虑 x>1x>1 的出现情况。
考虑弄出一些支配对，弄完以后将变成区间数颜色问题。在考虑 aia_i 的贡献时，如果 aia_i 作为分子，考虑整除分块，有 O(n)O(\sqrt{n}) 对支配对；如果 aia_i 作为分母，会产生 nai\dfrac{n}{a_i} 对支配对。前者的复杂度是可以接受的，所以可以正反扫两边，只考虑最新加入的数是较大数的贡献，这样就可以搞出 O(nn)O(n\sqrt{n}) 对支配对了。但是这个做法不仅需要 O(nn)O(n\sqrt{n}) 的空间，还需要 O(n)−O(1)O(\sqrt{n})-O(1) 的单点修改区间 max⁡\max 以用于找到值域区间最晚出现的数，不太可行。
还是考虑支配对，对于两个值 a<ba<b，若 a≤na\le \sqrt{n}，则考虑在 bb 处枚举 aa；若 a>na>\sqrt{n}，则考虑在 aa 处枚举 ⌊ba⌋\lfloor{\dfrac{b}a}\rfloor。这样总的枚举量是 O(nn)O(n\sqrt{n}) 的。注意到 a>na>\sqrt{n} 的部分查询的是 [ai,ai+a)[ai,ai+a) 的最大值，分块后恰好不会出现在同块，那么直接处理每个块的前后缀 max⁡\max 即可。由于查询的区间是不交的，每次询问暴力跳整块复杂度也是对的。但由于不能保证在后出现的位置枚举出支配对，需要正反各扫一遍，存支配对导致了 O(nn)O(n\sqrt{n}) 的空间复杂度。
改良一下枚举，发现 a≤na\le \sqrt{n} 的部分在 aa 处枚举也是可以的。但不是枚举 bb 的值，而是枚举到序列上 aa 上一次出现的位置。而 a>na>\sqrt{n} 的部分答案不超过 n\sqrt{n}，每个询问开一个 bitset 存可以接受。
所以最后的做法是：扫描线，考虑维护一个 lstxlst_x 表示答案 xx 最后出现的位置，然后只要查区间和（这里和区间数颜色一致，需要一个 O(1)O(1) 单点修改，O(n)O(\sqrt{n}) 区间和的分块，但是不算上 ans≤nans\le \sqrt{n} 的部分），然后对于 a≤na\le \sqrt{n} 的部分可以准确更新 lstlst。对于 a>na>\sqrt{n} 的部分就正反各扫一遍，维护出 ≤n\le \sqrt{n} 的数在每个询问中是否出现即可。
时间复杂度 O(nn)O(n\sqrt{n})，空间复杂度 O(nnw)O(\dfrac{n\sqrt{n}}w)，有点卡常。
CPP
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define getchar() (S==T&&(T=(S=BB)+fread(BB,1,1<<20,stdin),S==T)?EOF:*S++)
char BB[1<<20],*S=BB,*T=BB;
inline int read(){
    int x=0,c=getchar();
    while(c<48) c=getchar();
    while(c>47) x=(x*10)+(c^48),c=getchar();
    return x;
}
const int B=800,N=400000,C=N/B;
int n,m,a[N+5],lc[N+5],rc[N+5],ans[N+5],bl[N+5],sum[C+5],b[N+5],last[N+5];
int pmx[N+5],smx[N+5],mx[C+5],lst[N+5],mxx[N+5];
vector<array<int,2>> vr[N+5],vl[N+5];
bitset<C+5> vis[N+5];
int ss;
inline int qmax(int l,int r){
	if(bl[l]==bl[r]){
		int res=0;
		for(int i=l;i<=r;i++) res=max(res,mxx[i]);
		return res;
	}
	int res=max(pmx[r],smx[l]);
	for(int i=bl[l]+1;i<bl[r];i++) res=max(res,mx[i]);
	return res;
}
inline void add(int x,int y){sum[bl[x]]+=y,b[x]+=y;}
inline int calc(int l,int r,int res=0){for(int i=l;i<=r;i++) res+=b[i];return res;}
inline void upd(int x,int y){
	mx[bl[x]]=mxx[x]=y;
	for(int i=x;bl[i]==bl[x];i++) pmx[i]=y;
	for(int i=x;bl[i]==bl[x];i--) smx[i]=y;
}
inline int qsum(int l,int r){
	if(bl[l]==bl[r]) return calc(l,r); 
	int res=calc(l,bl[l]*B)+calc((bl[r]-1)*B+1,r);
	for(int i=bl[l]+1;i<bl[r];i++) res+=sum[i];
	return res;
}
int main(){
	for(int i=1;i<=N;i++) bl[i]=(i-1)/B+1;
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=read(),lc[i]=(a[i]==a[i-1]?lc[i-1]:i);
	for(int i=n;i;i--) rc[i]=(a[i]==a[i+1]?rc[i+1]:i);
	for(int i=1,l,r;i<=m;i++) l=read(),r=read(),ans[i]=1+(rc[l]<r),vr[r].push_back({l,i}),vl[n-l+1].push_back({n-r+1,i});
	for(int i=1;i<=n;i++){
		for(int j=1;j<=B&&j*2<=a[i];j++){
			int d=a[i]/j,p=last[j];
			if(d>C&&lst[d]<p) add(lst[d],-1),add(p,1);
			lst[d]=max(lst[d],p);
		}
		if(a[i]<=B)
			for(int j=i-1;j&&a[j]!=a[i];j--){
				int d=a[j]/a[i];
				if(d>C&&lst[d]<j) add(lst[d],-1),add(j,1);
				lst[d]=max(lst[d],j);
			}
		else for(int j=2;j*a[i]<=N;j++){
			int l=j*a[i],r=min(N,(j+1)*a[i]-1);
			lst[j]=max(lst[j],qmax(l,r));
		}
		for(auto x:vr[i]){
			int id=x[1],l=x[0];
			ans[id]+=qsum(l,i);
			for(int j=1;j<=C;j++)
				vis[id][j]=(vis[id][j]||lst[j]>=l);
		}
		last[a[i]]=i,upd(a[i],i);
	}	
	reverse(a+1,a+n+1),memset(pmx,0,sizeof(pmx)),memset(smx,0,sizeof(smx));
	memset(mx,0,sizeof(mx)),memset(lst,0,sizeof(lst)),memset(mxx,0,sizeof(mxx));
	for(int i=1;i<=n;i++){
		if(a[i]>B)
			for(int j=2;j*a[i]<=N;j++){
				int l=j*a[i],r=min(N,(j+1)*a[i]-1);
				lst[j]=max(lst[j],qmax(l,r));
			}
		for(auto x:vl[i]){
			int id=x[1],l=x[0];
			for(int j=1;j<=C;j++)
				vis[id][j]=(vis[id][j]||lst[j]>=l);
		}
		upd(a[i],i);
	}
	for(int i=1;i<=m;i++){
		for(int j=2;j<=C;j++) ans[i]+=vis[i][j];
		cout<<ans[i]<<'\n';
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...