自动搬运

查看原文

来自洛谷，原作者为

	yyandy /oh

搬运于2025-08-24 22:38:03，当前版本为作者最后更新于2022-08-15 20:07:22，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

直接判断不好搞，考虑两个数不互质的情况，这时这两个数至少有一个质因子相同。
所以在这题中一个数和他的质因子集合是等价的，
这启示我们建一个新序列，新序列里的每一个数都是原序列中某个数的质因子，
原序列中的一个数在新序列中对应一段区间，在原序列中询问一段区间也变为了新数列中询问一段区间。
由于每一个数的质因子不是很多，建出来的新序列也不会很长（大概算一下长度没有超过 $3\times 10^6$）。
于是我们就相当于要在新序列上求一段区间内有没有两个相同的数，如果有相同，就说明有不互质的数。
这个问题如果是不修改很容易做，只用记录对于每个数，上一个和它相同的数的位置，然后做一遍前缀 $\max$ 得到一个新数组，设为 $P$。
每次查询 $l,r$ 就相当于查询 $P_r$ 是否大于等于 $l$。
上面所说的大概就是这一题的做法，不懂的可以先做这题。
现在考虑如果动态修改该怎么做，
由于要动态修改，预处理行不通了，得寻找新方法。
对于每个值，为了快速找到上一个与它相同的数，我们要记录为该值的数的位置，由于要修改，还得支持快速插入删除定位，而这可以用 set 来完成。
之前的方法要维护前缀最大值，现在加上了单点修改，可以用线段树轻松维护。 常数非常大，有点卡，可能需要离散化一下，只降在询问或修改中出现的位置质因数分解构成新序列。 这样就可以大大减小新序列长度，就不用担心被卡了。

Code：

#include<bits/stdc++.h>
using namespace std;
const int N=1000000;
set<int> Pre[1100000];
int P[25],x,Max[24000000],t[1001000],M2[1001000],M1[3001000],g,st[1001000],ed[1001000],Mn[1001000],T[1001000],tot,tot2,A[9201000],n,Low[1201000],d[320000],e[320000],k;
char c[330000][3];
bool vis[1001000];
void Change(int x,int y,int l,int S,int k){
	if(x==y){
		Max[k]=S;
		return;
	}
	int mid=x+y>>1;
	if(l<=mid)Change(x,mid,l,S,k<<1);
	else Change(mid+1,y,l,S,(k<<1)|1);
	Max[k]=max(Max[k<<1],Max[(k<<1)|1]);
}
int Query(int x,int y,int l,int r,int k){
	if(x==l&&y==r)
		return Max[k];
	int mid=x+y>>1;
	if(l<=mid&&r>mid)return max(Query(x,mid,l,mid,k<<1),Query(mid+1,y,mid+1,r,(k<<1)|1));
	else if(l<=mid)return Query(x,mid,l,r,k<<1);
	else return Query(mid+1,y,l,r,(k<<1)|1);
}
bool query(int x,int y){
	if(st[x]>ed[y]||x>y)return 0;
	if(Query(1,tot2,st[x],ed[y],1)>=st[x])return 1;
	else return 0;
}
void del(int x){
	T[x]=0;
	for(int i=st[x];i<=ed[x];++i){
		Pre[A[i]].erase(i);
		auto it=Pre[A[i]].lower_bound(i);
		if(it!=Pre[A[i]].end()){
			if(it!=Pre[A[i]].begin()){
				int Q1=(*it);it--;
				int Q2=(*it);
				Change(1,tot2,Q1,Q2,1);
			}else Change(1,tot2,*it,0,1);
		}
		Change(1,tot2,i,0,1);
	}
}
void ins(int x){
	T[x]=1;
	for(int i=st[x];i<=ed[x];++i){
		auto it=Pre[A[i]].lower_bound(i);
		if(it!=Pre[A[i]].end())
			Change(1,tot2,*it,i,1);
		if(it!=Pre[A[i]].begin())
			it--,Change(1,tot2,i,*it,1);
		Pre[A[i]].insert(i);
	}
}
int main(){
	cin>>g>>n;
	memset(Low,63,sizeof(Low));
	for(int i=2;i<=N;++i)
		if(!vis[i])
			for(int j=i;j<=N;j+=i)
				vis[j]=1,Low[j]=min(Low[j],i);
	for(int i=1;i<=n;++i){
		scanf("%s%d",c[i],&d[i]);
		if(c[i][0]=='C')scanf("%d",&e[i]);
		if(c[i][0]=='S')t[d[i]]=1;
	}
	for(int i=1;i<=N;++i)
	if(t[i]){
		M1[i]=++k,M2[k]=i;tot=0;P[0]=-1;x=i;
		while(x>1){
			if(P[tot]!=Low[x])
				P[++tot]=Low[x];
			x/=Low[x];
		}
		st[k]=tot2+1;
		for(int i=1;i<=tot;++i)
			A[++tot2]=P[i];
		ed[k]=tot2;
	}
	for(int i=1;i<=n;++i){
		if(c[i][0]=='S'){	
			int p=M1[d[i]];
			if(T[p])del(p);
			else ins(p);
		}else{
			int x=lower_bound(M2+1,M2+k+1,d[i])-M2,y=upper_bound(M2+1,M2+k+1,e[i])-M2-1;
			if(query(x,y))puts("DA");		
			else puts("NE");
		}
	}
}