题解 SP13015 【CNTPRIME - Counting Primes 】

Setsugesuka · 2019-09-27 12:57:51 · 题解

阅读题意，发现题目要求我们维护两种操作，区间推平与统计区间素数个数，数据范围很小，用裸的 ODT 就可以解决了。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;

struct node
{
    int l,r,v;
    node(int L,int R=-1,int V=0):l(L),r(R),v(V) {}
    bool operator <(const node &o) const
    {
        return l<o.l;
    }
};

int prime[MAXN],p[MAXN],tot=0;
set<node> s;

inline void init()
{
    prime[1]=prime[0]=1;
    for(int i=2;i<=MAXN-10;i++)
    {
        if(prime[i]==0)
            p[++tot]=i;
        for(int j=1;j<=tot&&i*p[j]<=MAXN-10;j++)
        {
            prime[i*p[j]]=1;
            if(i%p[j]==0)
                break;
        }
    }
}

inline set<node>::iterator split(int pos)
{
    set<node>::iterator it=s.lower_bound(node(pos));
    if(it!=s.end()&&it->l==pos) return it;
    --it;
    int L=it->l,R=it->r,V=it->v;
    s.erase(it);
    s.insert(node(L,pos-1,V));
    return s.insert(node(pos,R,V)).first;
}

inline void assignval(int l,int r,int v)
{
    set<node>::iterator itr=split(r+1),itl=split(l);
    s.erase(itl,itr);
    s.insert(node(l,r,v));
}

inline int query(int l,int r)
{
    set<node>::iterator itr=split(r+1),itl=split(l);
    int ret=0;
    for(itl;itl!=itr;++itl)
    {
        if(!prime[itl->v])
            ret+=(itl->r-itl->l+1);
    }
    return ret;
}

int n,m,t;

int main()
{
    init();
    scanf("%d",&t);
    for(int cc=1;cc<=t;cc++)
    {
        printf("Case %d:\n",cc);
        scanf("%d %d",&n,&m);
        s.clear();
        for(int i=1;i<=n;i++)
        {
            int sr;
            scanf("%d",&sr);
            s.insert(node(i,i,sr));
        }
        while(m--)
        {
            int op;
            scanf("%d",&op);
            if(op==0)
            {
                int l,r,v;
                scanf("%d %d %d",&l,&r,&v);
                assignval(l,r,v);
            }
            else
            {
                int l,r;
                scanf("%d %d",&l,&r);
                printf("%d\n",query(l,r));
            }
        }
    }
    return 0;
}