ZOJ 3886

題意：

定義一種NicoNico數(shù)x，x有下面特征：
全部不大于x且與x互質(zhì)的數(shù)成等差數(shù)列，如x = 5 ，與5互素且不大于5的數(shù)1,2,3,4成等差數(shù)列。則5是一個NicoNico數(shù)。

再定義三種操作：
1.南小鳥詢問[L, R]內(nèi)有多少個NicoNico數(shù)；
2.果皇把[L, R]內(nèi)的數(shù)全部對v取余；
3.果皇將第K個數(shù)換成X。

然后給你一個數(shù)列，并對這個數(shù)列運行若干操作

思路：

這樣的問題果斷要用LoveLive樹線段樹來做！
首先我們通過打表發(fā)現(xiàn)NicoNico數(shù)僅僅可能是素數(shù)。2的n次冪。6，所以能夠先預(yù)處理，對范圍內(nèi)的全部NicoNico數(shù)進行標記。
建樹過程：假設(shè)是NicoNico數(shù)則節(jié)點值為1，不是則為0。

更新操作1：對區(qū)間內(nèi)的數(shù)進行取模即是區(qū)間改動。這里能夠優(yōu)化一下，假設(shè)區(qū)間最大值小于v，則不須要改動。

更新操作2：即單點改動。

查詢操作：輸出詢問區(qū)間和就可以。

時間復(fù)雜度：
預(yù)處理：O(x)
建樹：O(n)
查詢與更新：操作次數(shù)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;elseHonoka_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;elseHonoka_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;elseHonoka_sum[root] = 0;return ;}int mid = ( l + r ) / 2 ;if( mid >= pos )Honoka2( pos , x , lson );elseHonoka2( 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; }

總結(jié)

以上是生活随笔為你收集整理的ZOJ 3886 Nico Number（筛素数+Love（线）Live（段）树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。