数学家的迷题

题意：
1：将 $a[id]$ 的值改为 $x$ 。
2：令 $t=a[l]×a[l+1]×...×a[r−1]×a[r]$ ，求t能被多少个不同的素数整除。

题解：
本题有两种解法，带修莫队和线段树，带修莫队的话需要开个O3提提速，不然会T一个点。

1.带修莫队
题目不是5e4的范围吗，带修莫队会卡时间？
因为莫队移动的操作时间复杂度为O(1)，但是这个移动的时间复杂度却不是O(1)，应该是一个10左右的常数的大小，再加上vector本身就有点慢，所以会有点卡时间。

带修莫队的话，其实就可以当场是一个比较模板的题目了，只不过一个位置上的数字变成了好几个而已。

代码：

#pragma GCC optimize(3)
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>

#define endl '\n'

using namespace std;
const int maxn=1e5+10;

bool vis[maxn];
int prime[maxn], tot;

void get_prime(int n) {
    vis[1] = true;
    for(int i = 2; i <= n; ++ i) {
        if (!vis[i]) prime[++tot] = i;
        for(int j = 1; prime[j] <= n/i; ++ j) {
            vis[prime[j] * i] = true;
            if (i % prime[j] == 0) break;
        }
    }
}
vector<int> pri[maxn];
struct node{
    int l,r,id,t;
}q[maxn];
pair<int,vector<int> > c[maxn];
int be[maxn];
int cntq,cntc,sz;
int cnt[maxn];

struct rule{
    bool operator ()(const node & x,const node & y)const{
        if(be[x.l]!=be[y.l])return x.l<y.l;
        if(be[x.r]!=be[y.r])return x.r<y.r;
        return x.t<y.t;
    }
};
int sum;
int l=0,r,t;
void add(int x){
    for(auto i:pri[x]){
        if(++cnt[i]==1) sum++;
    }
}
void sub(int x){
    for(auto i:pri[x]){
        if(--cnt[i]==0) sum--;
    }
}
void upt(int x){
    if(c[x].first>=l&&c[x].first<=r){
        for(auto i:pri[c[x].first]){
            if(--cnt[i]==0) sum--;
        }
        for(auto i:c[x].second){
            if(++cnt[i]==1) sum++;
        }
    }
    swap(pri[c[x].first],c[x].second);
}
int ans[maxn];
int main(){
    get_prime(100000);
    int n,m;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    sz=pow(n,2.0/3.0);
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        be[i]=i/sz+1;
        for(int k=1;k<=tot;k++){
            if(x==1) break;
            if(vis[x]==false){
                pri[i].push_back(x);
                break;
            }
            bool flag=false;
            while(x%prime[k]==0){
                x/=prime[k];
                flag=true;
            }
            if(flag){
                pri[i].push_back(prime[k]);
            }
        }
    }

    for(int i=1;i<=m;i++){
        int opt,x,y;
        cin>>opt>>x>>y;
        if(opt==1){
            c[++cntc].first=x;
            //c[cntc].second=y;

            for(int k=1;k<=tot;k++){
                if(y==1) break;
                if(vis[y]==false){
                    c[cntc].second.push_back(y);
                    break;
                }
                bool flag=false;
                while(y%prime[k]==0){
                    y/=prime[k];
                    flag=true;
                }
                if(flag){
                    c[cntc].second.push_back(prime[k]);
                }
            }
        }
        else{
            q[++cntq].l=x;
            q[cntq].r=y;
            q[cntq].t=cntc;
            q[cntq].id=cntq;
        }
    }

    sort(q+1,q+cntq+1,rule());


    for(int i=1;i<=cntq;i++){
        while(r<q[i].r) add(++r);
        while(l>q[i].l) add(--l);
        while(r>q[i].r) sub(r--);
        while(l<q[i].l) sub(l++);
        while(t<q[i].t) upt(++t);
        while(t>q[i].t) upt(t--);


        ans[q[i].id]=sum;
    }
    for(int i=1;i<=cntq;i++) cout<<ans[i]<<endl;


}

2.线段树

线段树上每个点维护一个bitset即可。
最原始的线段树是求得和，这里的话把求和改成求或即可。
注意要压缩一下bitset的使用空间，1e5大约有1e4个素数，我们不能开1e5的bitset，我们只需要开1e4的bitset即可，把1e4的素数按照大小安排在每个位置，类似于离散化。

数学家的迷题

全站热榜