P8327 Radio 题解

· · 题解

直接判断不好搞，考虑两个数不互质的情况，这时这两个数至少有一个质因子相同。
所以在这题中一个数和他的质因子集合是等价的，
这启示我们建一个新序列，新序列里的每一个数都是原序列中某个数的质因子，
原序列中的一个数在新序列中对应一段区间，在原序列中询问一段区间也变为了新数列中询问一段区间。
由于每一个数的质因子不是很多，建出来的新序列也不会很长（大概算一下长度没有超过 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");
        }
    }
}