SP13015 CNTPRIME - Counting Primes 题解

· · 题解

更富有激情的阅读体验：SP13015 CNTPRIME - Counting Primes 题解

亲，这是本蒟蒻的第一篇题解，记得多多点赞支持呦。

一道不错的 ODT 练手题，题目传送门： SP13015 CNTPRIME - Counting Primes。

翻译是我写的

接下来将会从零开始学习 ODT，会 ODT 的大爷可以跳转到正文部分。

ODT

ODT，全名为 Old Driver Tree，又名珂朵莉树，是毒瘤 lxl 发明的暴力数据机构。其本质思想是通过 STL 的 set 维护权值相同的区间，达到优化暴力时间复杂度的目的。其核心函数是 split 和 assign，也就是分裂区间和区间推平。

注意: 因为它的时间复杂度维护区间的数量越少越优，所以只能做有区间推平较多的题目，也就是需要数据随机

接下来会具体讲解 ODT：

ODT 的建立

定义一个 struct，维护每一个权值相同的区间的左端点、右端点和权值。因为要存到 set 中， 所以要重载小于号。这里我们按照左端点升序排序。在后面的分裂操作会解释按左端点排序的原因。

代码：

struct ODT {
    int l, r, val;
    ODT(int _l = 0, int _r = 0, int _val = 0): l(_l), r(_r), val(_val) {return;}
    bool operator < (const ODT &x) const {
        return l < x.l;
    }
}
std::set<ODT> tree;

分裂

分裂是 ODT 最重要的操作，ODT 的所有衍生操作都是以分裂操作为基础的。

在定义是我们按照左端点升序排序，就是为了分裂操作方便。我们分裂操作要求支持分裂出一个以 x 为左端点的区间，并传回它的指针。因为我们是按照左端点升序排序，所以可以直接用 set 自带的 lower_bound 查询。注意不要使用 algorithm 的 lower_bound 查询，个别题目会 TLE。

如果我们没有找到以 x 为左端点的区间，我们可以将找到的区间的上一个区间分裂。因为 lower_bound 的性质，我们分裂的这个区间的左端点一定小于等于 x，所以可以进行分裂。

代码：

#define It std::set<ODT>:: iterator

It split(int x) {
    It it = tree.lower_bound(x);
    if (it != tree.end() && it->l == x) return it;
    it--; int l = it->l, r = it->r, val = it->val;
    tree.erase(it); tree.insert(ODT(l, x - 1, val));
    return tree.insert(ODT(x, r, val)).first;
}

区间推平

ODT 维护复杂度正确性的重要操作就是区间推平。这个操作很好写但也很容易错。大佬 泥土笨笨 曾在 ODT 博客 珂朵莉树模板CF896C Willem, Chtholly and Seniorious题解 指正了该题目题解区一群题解区间推平的错误。

assign 的实现是通过将 r + 1 和 l 的区间分裂出来，再通过 set 的 erase 操作删除两个区间之间的所有区间，并插入一个大区间就可以了

注意：正如泥土笨笨所说，应该先分裂右端点再分裂左端点。因为如果先分裂左端点，分裂右端点时可能会影响左端点的区间的状态。

如图所示：

这是一棵区间推平前的 ODT。现在我们要将 [2, 4] 区间推平。如果我们先分裂左端点：

此时左端点分裂出的区间为第二个区间。再分裂右端点：

此时我们可以看到之前的区间二被分裂了，也就意味着那个指针被删除了。之后对那个区间的调用都是无效调用。如果先分裂左再分裂右就有可能 RE。

代码：

#define It std::set<ODT>::iterator

void assign(int l, int r, int val) {
    It itr = split(r + 1), itl = split(l);
    tree.erase(itl, itr); tree.insert(ODT(l, r, val));
    return;
}

正文

啊哈哈哈，正文来喽。

这个题算比较好的 ODT 练手题。可以先欧拉筛 O(\max{a_i}) 预处理所有的质数。然后只需要维护分裂、区间推平和查询操作即可。

多组数据记得清空呦~~

代码：

#include <bits/stdc++.h>
#define It set<ODT>::iterator

using namespace std;

const int N = 2e6 + 10;
int prime[N], pcnt; bool not_prime[N];

void eular() {
    not_prime[0] = not_prime[1] = true;
    for (int i = 2; i <= N; i++) {
        if (!not_prime[i]) {
            prime[++pcnt] = i;
        }
        for (int j = 1; j <= pcnt && i * prime[j] <= N; j++) {
            not_prime[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
    return;
}

struct ODT {
    int l, r;
    mutable int val;
    bool operator < (const ODT &x) const {
        return l < x.l;
    }
    ODT(int _l = 0, int _r = 0, int _val = 0):l(_l), r(_r), val(_val){return;}
};
set<ODT> tree;

It split(int x) {
    It it = tree.lower_bound(ODT(x));
    if (it != tree.end() && it->l == x) return it;
    it--; int l = it->l, r = it->r, val = it->val;
    tree.erase(it); tree.insert(ODT(l, x - 1, val));
    return tree.insert(ODT(x, r, val)).first;
}

void assign(int l, int r, int val) {
    It itr = split(r + 1), itl = split(l);
    tree.erase(itl, itr);
    tree.insert(ODT(l, r, val));
    return;
}

int query(int l, int r) {
    int ans = 0; It itr = split(r + 1), itl = split(l);
    for (It it = itl; it != itr; it++) {
        if (!not_prime[it->val]) ans += it->r - it->l + 1;
    }
    return ans;
}

int t, n, q;

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    eular();
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cout << "Case " << i << ':' << endl;
        cin >> n >> q;
        tree.clear();
        for (int j = 1, x; j <= n; j++)
            cin >> x, tree.insert(ODT(j, j, x));
        for (int j = 1, op, x, y, v; j <= q; j++) {
            cin >> op >> x >> y;
            if (!op) {
                cin >> v;
                assign(x, y, v);
            }
            else {
                cout << query(x, y) << endl;
            }
        }
    }
    return 0;
}

完结撒花（超小声