ZOJ 3886 Nico Number（筛素数+Love（线）Live（段）树）

题意：

思路：

这样的问题果断要用线段树来做！

首先我们通过打表发现NicoNico数仅仅可能是素数。2的n次幂。6，所以能够先预处理，对范围内的全部NicoNico数进行标记。

建树过程：假设是NicoNico数则节点值为1，不是则为0。

更新操作1：对区间内的数进行取模即是区间改动。这里能够优化一下，假设区间最大值小于v，则不须要改动。

更新操作2：即单点改动。

查询操作：输出询问区间和就可以。

时间复杂度：

预处理：O(x)

建树：O(n)

查询与更新：操作次数O(m)，每次操作O(logn)加起来是O(mlogn)

羞耻的代码君：

这次代码风格。

。

重在理解重在理解。

/*

* @author FreeWifi_novicer

* language : C++/C

*/

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<string>

#include<map>

#include<set>

#include<vector>

#include<queue>

using namespace std;

#define clr( x , y ) memset(x,y,sizeof(x))

#define cls( x ) memset(x,0,sizeof(x))

#define mp make_pair

#define pb push_back

#define lson l , mid , root << 1

#define rson mid + 1 , r , root << 1 | 1

typedef long long lint;

typedef long long ll;

typedef long long LL;

const int maxNico = 1e7 + 500 ;

const int maxHonoka = 1e5 + 7 ;

int Honoka_max[10 * maxHonoka] ;

int Honoka_sum[10 * maxHonoka] ;

bool Nico_prime[maxNico];

map<int , int> NicoNicoNi;

/* にっこにっこにー☆あなたのハートににこにこにー 笑颜届ける矢澤にこにこー にこにーって覚えてラブにこー */

void init(){

    NicoNicoNi[0] = NicoNicoNi[6] = 1;

    for( int i = 0 ; i <= 31 ; i++ ){

        NicoNicoNi[( 1 << i )] = 1;

    }

    cls( Nico_prime );

    for( int  i = 2 ; i * i <= maxNico ; i++ ){

        if( !Nico_prime[i] )

            for( int j = i * i ; j <= maxNico ; j+=i )

                Nico_prime[j] = 1;

    }

    for( int i = 2 ; i <= maxNico ; i++ )

        if( !Nico_prime[i] ) NicoNicoNi[i] = 1;

}

void push_Yazawa( int root ){

    Honoka_max[root] = max( Honoka_max[ root << 1 ] , Honoka_max[ root << 1 | 1 ] );

    Honoka_sum[root] = Honoka_sum[ root << 1 ] + Honoka_sum[ root << 1 | 1 ] ;

}

void build_Kotori( int l , int r , int root ){

    if( l == r ){

        scanf( "%d" , &Honoka_max[root] );

        if( NicoNicoNi[Honoka_max[root]] )

            Honoka_sum[root] = 1;

        else

            Honoka_sum[root] = 0;

        return ;

    }

    int mid = ( l + r ) / 2 ;

    build_Kotori( lson );

    build_Kotori( rson );

    push_Yazawa( root );

}

void Honoka1( int ql , int qr , int x , int l , int r , int root ){

    if( qr < l || ql > r )

        return ;

    if( Honoka_max[root] < x)

        return ;

    if( l == r ){

        Honoka_max[root] %= x ;

        if( NicoNicoNi[Honoka_max[root]] )

            Honoka_sum[root] = 1;

        else

            Honoka_sum[root] = 0;

        return ;

    }

    int mid = ( l + r ) / 2 ;

    Honoka1( ql , qr , x , lson );

    Honoka1( ql , qr , x , rson );

    push_Yazawa( root );

}

void Honoka2( int pos , int x , int l , int r , int root ){

    if( l == pos && r == pos ){

        Honoka_max[root] = x ;

        if( NicoNicoNi[x] )

            Honoka_sum[root] = 1;

        else

            Honoka_sum[root] = 0;

        return ;

    }

    int mid = ( l + r ) / 2 ;

    if( mid >= pos )

        Honoka2( pos , x , lson );

    else

        Honoka2( pos , x , rson );

    push_Yazawa( root );

}

int Kotori( int ql , int qr , int l , int r , int root ){

    if( ql > r || qr < l )

        return 0 ;

    if( ql <= l && qr >= r )

        return Honoka_sum[root];

    int res = 0 ;

    int mid = ( l + r ) / 2 ;

    if( ql <= mid )

        res += Kotori( ql , qr , lson ) ;

    if( qr > mid )

        res += Kotori( ql , qr , rson ) ;

    return res;

}

int main(){

  //freopen("input.txt","r",stdin);

    init();

    int n ;

    while( cin >> n ){

        build_Kotori( 1 , n , 1 ) ;

        int m ;

        cin >> m ;

        for( int i = 1 ; i <= m ; i++ ){

            int num ;

            scanf( "%d" , &num );

            if( num == 1 ){

                int left , right ;

                scanf( "%d%d" , &left , &right ) ;

                printf( "%d\n" , Kotori( left , right , 1 , n , 1 ));

            }

            else if( num == 2 ){

                int left , right , mod ;

                scanf( "%d%d%d" , &left , &right , &mod ) ;

                Honoka1( left , right , mod , 1 , n , 1 ) ;

            }

            else if( num == 3 ){

                int pos , x ;

                scanf( "%d%d" , &pos , &x ) ;

                Honoka2( pos , x , 1 , n , 1 ) ;

            }

        }

    }

    return 0;

}