自动搬运

查看原文

来自洛谷，原作者为

	冰糖鸽子 还不是能说晚安的时候哦。

搬运于2025-08-24 22:12:44，当前版本为作者最后更新于2022-01-13 11:14:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

为什么题解全是状压 ST 表什么的捏。

来一个前缀和题解。

Part 1：处理原数

设 $b$ 数组存储的是这 $m$ 个原数。

原数可能会有重复（比如样例 $1$），所以先把 $b$ 去重。由于 $m$ 很小所以可以暴力 $\operatorname{O}(m^2)$ 实现。

注意到每个原数也可能可以被其他原数消灭，设 $b_i$ 可以被 $b_j$ 消灭（$i \ne j$）。

每个能被 $b_i$ 消灭的数，由于其被除到 $b_i$ 后一定能被除到 $b_j$，所以一定也能被 $b_j$ 消灭。

有结论：若 $x$ 能被 $y$ 消灭且 $y$ 能被 $z$ 消灭，则 $x$ 能被 $z$ 消灭。

当 $b_i$ 可以被 $b_j$ 消灭时，$b_i$ 可以消灭的数集 是 $b_j$ 可以消灭的数集 的子集。于是 $b_i$ 就能被 $b_j$ 代替。

所以我们二次处理 $b$ 数组，对所有 $b_i$，如果能找到一个可以消灭 $b_i$ 的 $b_j$（$i \ne j$），则删去 $b_i$。

处理过后，每个 $a_i$ 只能被 $0$ 或 $1$ 个原数消灭，$\operatorname{O}(m\log a_i)$ 求出这个原数 $c_i$（因为 $d$ 的值有变等原因并跑不满）。

这一部分总复杂度 $\operatorname{O}(m^2+m^2\log V+mn\log V) = \operatorname{O}(mn\log V)$ （$V$ 为 $a_i,b_i$ 上界）。

Part 2：处理询问

经过 $\text{Part 1}$ 的处理，得到了 $c$ 数组，而询问就变成了区间数颜色，并且颜色数 $\leq60$。

则有一个显然的做法：枚举每个原数，判断区间中原数是否存在，存在则答案加一。

可以先前缀和一遍，$sum_{i,j}$ 表示 $c$ 的前 $i$ 个元素中第 $j$ 个原数出现的次数。然后 $\operatorname{O}(1)$ 实现判断区间中原数是否存在。

最后输出答案即可。

这一部分复杂度为 $\operatorname{O}(qm)$。

坑点：

• map 存原数可能会比枚举原数更慢。

• $sum$ 数组如果是 long long 类型会 MLE。

AC代码：

// Problem: P5629 【AFOI-19】区间与除法
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5629
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://cpeditor.org)
// Auther: Sugar_Pigeon(227728)

#include <bits/stdc++.h>
using namespace std;
#define M 1000006
#define INT long long
INT n,m,ox,oy,nm,d,q,a[M],nd[M],b[M],ans,c[M],hav0;
int sum[M][65];
void calc(INT x) {
	INT y=a[x];
	if(hav0) {nd[x]=0;return;}
	while(y) {
		for(INT i=1;i<=m;i++) {
			if(b[i]==y) {
				nd[x]=y;
				return;
			}
		}
		y/=d;
	}
	if(!nd[x]) nd[x]=-1;
	return;
}
bool dop(INT x) {
	while(x)
	{
		x/=d;
		for(INT i=1;i<=m;i++)
			if(b[i]==x)
				return 1;
	}
	return 0;
}
signed main() {
	scanf("%lld%lld%lld%lld",&n,&m,&d,&q);
	for(INT i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(INT i=1;i<=m;i++) {
		scanf("%lld",&b[i]);
		for(INT j=1;j<i;j++) {
			if(b[j]==b[i]) {
				m--,i--;
				break;
			}
		}
	}
	sort(b+1,b+m+1);
	for(INT i=m;i>=1;i--) {
		if(!dop(b[i])) {
			c[++nm]=b[i];
		}
	}
	m=nm;
	for(INT i=1;i<=m;i++)
		b[i]=c[i],hav0=((hav0||!b[i])?1:0);
	for(INT i=1;i<=n;i++)
		calc(i);
	for(INT i=1;i<=n;i++)
		for(INT j=1;j<=m;j++)
			sum[i][j]=sum[i-1][j]+(nd[i]==b[j]?1:0);
	for(INT Q=1;Q<=q;Q++) {
		scanf("%lld%lld",&ox,&oy);
		ans=0;
		for(INT i=1;i<=m;i++)
			if(sum[oy][i]-sum[ox-1][i])
				ans++;
		printf("%lld\n",ans);
	}
	return 0;
}