首页 > 其他分享 >SP13015 CNTPRIME -Counting Primes

SP13015 CNTPRIME -Counting Primes

时间:2023-10-23 12:01:59浏览次数:36  
标签:return int tr cin CNTPRIME tag ls Primes Counting

\(CNTPRIME\) - \(Counting\) \(Primes\)

题目描述

给定初始序列 \(A\),然后对原序列有以下操作:

  • 操作 \(1\):0 l r v 将区间\([l,r]\) 全赋值为\(v\)。
  • 操作 \(2\):1 l r 查询区间\([l,r]\)

注意:多组测试和特殊的输出。

题目分析:

就是一道板子题,首先我们先用欧拉筛筛出值域 \([2,10^6]\)内的素数并开桶打标记(实际上一个欧拉筛就行了)。

此时,线段树维护的是当前区间内质数的个数,我们可以将操作 \(1\)

  • 若 \(v\) 属于质数,则将区间 \([l,r]\) 内的数全赋值成 \(1\)。
  • 若 \(v\) 不属于质数,则将区间 \([l,r]\) 内的数全赋值成 \(0\)。

那么,操作 \(2\)

时间复杂度,\(O(nlgn)\)。

线段树解法

// 编译器选择GCC C++14

#include <bits/stdc++.h>
using namespace std;

#define ls u << 1
#define rs u << 1 | 1
// 欧拉筛
const int N = 1e6 + 10;
int primes[N], cnt; // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] * i <= n; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
int a[N];

// 线段树
struct Node {
    int l, r; // 区间范围
    int sum;  // 区间和
    int tag;  // 懒标记
} tr[N << 2];

void pushup(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    tr[u].tag = 0; // 多组测试数据,需要清零
    if (l == r) {
        tr[u].sum = !st[a[l]]; // 如果a[l]是质数,那么!st[a[l]]==1,则单节点的tr[u].sum=1.否则为0
        return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(u);
}

// 修改u节点的懒标记和统计信息
void update(int u, int tag) {
    tr[u].tag = tag;
    if (tr[u].tag == 1) tr[u].sum = tr[u].r - tr[u].l + 1;
    if (tr[u].tag == 2) tr[u].sum = 0;
}

void pushdown(int u) {
    // 向左儿子传递
    update(ls, tr[u].tag);
    // 向左儿子传递
    update(rs, tr[u].tag);
    // 终于完成向左右儿子传递懒标记的任务,将自己的懒标记清除
    tr[u].tag = 0;
}

void modify(int u, int l, int r, int tag) {
    if (tr[u].tag == tag) return; // 剪枝

    if (l <= tr[u].l && r >= tr[u].r) {
        if (tag == 1) {
            tr[u].sum = tr[u].r - tr[u].l + 1;
            tr[u].tag = 1;
            return;
        }
        if (tag == 2) {
            tr[u].sum = 0;
            tr[u].tag = tag;
            return;
        }
    }
    if (tr[u].tag) pushdown(u);
    if (tr[ls].r >= l) modify(ls, l, r, tag);
    if (tr[rs].l <= r) modify(rs, l, r, tag);
    pushup(u);
}

int query(int u, int l, int r) {
    if (tr[u].sum == 0) return 0; // 剪枝,优化
    if (l <= tr[u].l && r >= tr[u].r) return tr[u].sum;

    if (tr[u].tag) pushdown(u);
    if (tr[rs].l > r) return query(ls, l, r);
    if (tr[ls].r < l) return query(rs, l, r);
    return query(ls, l, r) + query(rs, l, r);
}

/*
Case 1:
1
4
*/
int main() {
#ifndef ONLINE_JUDGE
    freopen("SP13015.in", "r", stdin);
#endif
    // 加快读入
    ios::sync_with_stdio(false), cin.tie(0);

    // 欧拉筛,筛出1e6以内所有的质数
    get_primes(1e6);

    int T;
    cin >> T;
    for (int x = 1; x <= T; x++) {
        cout << "Case " << x << ':' << endl;
        int n, q;
        cin >> n >> q;
        for (int i = 1; i <= n; i++) cin >> a[i];
        // 构建线段树
        build(1, 1, n);

        while (q--) {
            int op;
            cin >> op;
            if (op == 0) { // 全赋值为v
                int l, r, v;
                cin >> l >> r >> v;
                int tag;
                if (!st[v])
                    tag = 1;
                else
                    tag = 2;
                modify(1, l, r, tag); // 如果v是质数,那么整个区间都设置为1.否则,全部设置为0
            }
            if (op == 1) { // 查询质数个数
                int l, r;
                cin >> l >> r;
                cout << query(1, l, r) << endl;
            }
        }
    }
    return 0;
}

柯朵莉树解法

#include <bits/stdc++.h>
using namespace std;

// 欧拉筛
const int N = 1e6 + 10;
int primes[N], cnt; // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] * i <= n; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

// 柯朵莉树模板
struct Node {
    int l, r;      // l和r表示这一段的起点和终点
    mutable int v; // v表示这一段上所有元素相同的值是多少,注意关键字 mutable,使得set中结构体属性可修改
    bool operator<(const Node &b) const {
        return l < b.l; // 规定按照每段的左端点排序
    }
};
set<Node> s; // 柯朵莉树的区间集合

// 分裂:[l,x-1],[x,r]
set<Node>::iterator split(int x) {
    auto it = s.lower_bound({x});
    if (it != s.end() && it->l == x) return it; // 一击命中
    it--;                                       // 没有找到就减1个继续找
    if (it->r < x) return s.end();              // 真的没找到,返回s.end()

    int l = it->l, r = it->r, v = it->v; // 没有被返回,说明找到了,记录下来,防止后面删除时被破坏
    s.erase(it);                         // 删除整个区间
    s.insert({l, x - 1, v});             //[l,x-1]拆分
    // insert函数返回pair,其中的first是新插入结点的迭代器
    return s.insert({x, r, v}).first; //[x,r]拆分
}

// 区间加
void add(int l, int r, int v) {
    // 必须先计算itr,后计算itl
    auto R = split(r + 1), L = split(l);
    for (auto it = L; it != R; it++) it->v += v;
}
// 区间赋值
void assign(int l, int r, int v) {
    auto R = split(r + 1), L = split(l);
    s.erase(L, R);       // 删除旧区间
    s.insert({l, r, v}); // 增加新区间
}

int query(int l, int r) {
    int res = 0;
    auto R = split(r + 1), L = split(l);
    for (auto it = L; it != R; it++) {
        if (!st[it->v]) res += it->r - it->l + 1;
    }
    return res;
}

int t, n, q;
/*
Case 1:
1
4
*/

int main() {
#ifndef ONLINE_JUDGE
    freopen("SP13015.in", "r", stdin);
#endif
    ios::sync_with_stdio(false), cin.tie(0);
    get_primes(1e6);

    cin >> t;
    for (int i = 1; i <= t; i++) {
        cout << "Case " << i << ':' << endl;
        cin >> n >> q;
        s.clear();

        for (int j = 1, x; j <= n; j++)
            cin >> x, s.insert({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;
}



标签:return,int,tr,cin,CNTPRIME,tag,ls,Primes,Counting
From: https://blog.51cto.com/u_3044148/7985501

相关文章

  • 洛谷题解 | AT_abc321_c Primes on Interval
    目录题目翻译题目描述输入格式输出格式样例#1样例输入#1样例输出#1样例#2样例输入#2样例输出#2样例#3样例输入#3样例输出#3题目简化题目思路AC代码题目翻译【题目描述】你决定用素数定理来做一个调查.众所周知,素数又被称为质数,其含义就是除了数字一和本身之外不能......
  • Codeforces Round 884 (Div. 1 + Div. 2) B. Permutations & Primes
    给一个正整数\(n\),你需要构造一个\(n\)的排列\(p_1,p_2,\cdots,p_n\)。对于排列\(p\)的每个子段\([l,r]\),\(mex_{i=l}^{r}a_i\)的结果为质数的次数尽可能多。此处的\(mex\)最小排除值最低为\(1\)而非\(0\)。不难想到,小质数\(2,3\)容易构造。于是有......
  • [USACO17JAN] Promotion Counting P 题解
    [USACO17JAN]PromotionCountingP题解前言好久没写题解了,今天趁我心情好赶紧水一篇。思路首先拿到这题,关键词检索:子树,比\(p_i\)大的,树状数组!现在考虑如何去掉其他子树的贡献……emm,我直接在算贡献的时候去掉其他子树的贡献不就好了!当然,暴力去贡献复杂度肯定爆炸,这里考虑......
  • G. Counting Graphs
    G.CountingGraphs题意:添加几条线段,使得图仍保持原先的最小生成树通过画图我们发现,要添加u->v的线段,线段必须大于u->v的路径内的最大值,不然会破坏原先的最小生成树。那么该怎么维护路径内的最大值呢?方法:1.我们对边的大小进行排序,这样当前边一定大于等于之前的边,只要对当前边......
  • AtCoder Beginner Contest 288 Ex A Nameless Counting Problem
    洛谷传送门AtCoder传送门考虑到规定单调不降比较难搞。先设\(g_t\)为长度为\(t\)的满足条件的序列个数(可重且有顺序)。求这个可以设个dp,\(f_{d,i}\)表示考虑到从高到低第\(d\)位,当前\(t\)个数中有\(i\)个仍然顶上界,并且之前的位都满足异或分别等于\(X\)的限制。......
  • 挑战程序设计竞赛 2.1章习题 POJ 2386 Lake Counting
    https://vjudge.net/problem/POJ-2386由于最近的降雨,水在农夫约翰的田地上聚集,在这片田地中,每个方块都被表示为一个NxM(1≤N≤100;1≤M≤100)的矩形。每个方块可以是水('W')或干地('.')。农夫约翰想弄清楚他的田地上形成了多少个池塘。池塘是由含有水的相连方块组成的集合,......
  • counting题解
    \(N,M\le1e7\)接着反射容斥,考虑这道题怎么做如果去枚举不动步数,加上反射容斥,直接T飞了把-1/0/1操作转换一下,就成了0/1/2如果没有限制(不能<0或>m),n步方案就是\((1+x+x^2)^n\)设\(H=1+x+x^2\quadF=H^n\)那么对两边求导:\[nH^{n-1}H'=F'\]\[F'H=nFH'\]我们知道\[H=1+x+x^2......
  • 洛谷题解 | AT_abc321_c Primes on Interval
    目录题目翻译题目描述输入格式输出格式样例#1样例输入#1样例输出#1样例#2样例输入#2样例输出#2样例#3样例输入#3样例输出#3题目简化题目思路AC代码题目翻译【题目描述】你决定用素数定理来做一个调查.众所周知,素数又被称为质数,其含义就是除了数字一和本身之外不能......
  • CF1857G Counting Graphs
    题目链接考虑每条非树边的取值,显然不能小于等于该边与树边形成的环中的最大值(当然这条非树边也可以不存在),所以每条非树边的取值范围就是\(S-max(w)+1\)(\(+1\)的原因是该边可能不存在)。暴力枚举肯定会超时,考虑优化。发现\(kruskal\)算法获得最小生成树的过程中,按从小到......
  • 一个树状数组求逆序对的进阶 [USACO17JAN] Promotion Counting P
    题面就这样,就是在树上求一个逆序对但是我笨笨地求了对于每一个下属有几个上司能力比他低还一遍就写对了,结果发现看错题目了难得一遍过,但是没有完全过 ......