SP13015 题解

· · 题解

思路

有区间推平操作，显然可以考虑 ODT。

ODT 维护的是这一段里面的值，查询的时候再判断一下是不是质数就行了，质数的话，用个埃氏筛就行了，或者直接 \sqrt{x} 也能过。

ODT 的博客的话，我推荐这篇。

代码

代码：

#include<bits/stdc++.h>
#define init auto itr = split(r + 1), itl = split(l);
#define int long long

using namespace std;

const int mod = 1e9 + 7;
const int N = 1e6 + 5;

int t, n, m;
int a[N];

bool vis[10000005];

struct Node{
    int l, r;
    mutable int val;

    Node(int L, int R = -1, int v = 0){
        l = L;
        r = R;
        val = v;
    }

    bool operator<(const Node &x) const{
        return l < x.l;
    }
};

set<Node> odt;

void E_prime(int x){   //埃氏筛
    vis[1] = vis[0] = true;   //写不写都没问题
    for(int i = 2; i <= sqrt(x); i++){
        if(!vis[i]){
            for(int j = i * i; j <= x; j += i){
                vis[j] = true;
            }
        }
    }
}

auto split(int pos){   //ODT 操作
    auto it = odt.lower_bound(Node(pos));
    if(it != odt.end() && it -> l == pos){
        return it;
    }
    it--;
    int l = it -> l, r = it -> r, val = it -> val;
    odt.erase(it);
    odt.insert(Node(l, pos - 1, val));
    return odt.insert(Node(pos, r, val)).first;
}

void assign(int l, int r, int val){
    init
    odt.erase(itl, itr);
    odt.insert(Node(l, r, val));
}

int query(int l, int r){
    init
    int ans = 0;
    for(auto i = itl; i != itr; i++){
        if(!vis[(i -> val)]){   //如果为质数
            ans += (i -> r) - (i -> l) + 1;
        }
    }
    return ans;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    cin >> t;
    E_prime(10000000);  //这里筛 1e6 就行了
    for(int T = 1; T <= t; T++){
        odt.clear();
        cin >> n >> m;
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            odt.insert(Node(i, i, a[i]));
        }
        cout << "Case " << T << ":\n";   //这里建议复制
        while(m--){
            int op, x, y, v;
            cin >> op >> x >> y;
            if(op == 0){
                cin >> v;
                assign(x, y, v);
            }
            else{
                cout << query(x, y) << '\n';
            }
        }
    }
    return 0;
}