題目地址：ZJU 3886
這個題需要想到一點，因為對一個數x不斷取模的話，而且設定他小于模才會進行取余操作的話，那么最多只會進行logx次，因為每次取模都會使x最少折半。然后想到了這點就很好做了。對于區間取模更新操作可以直接暴力更新，維護一個最大值，如果這個區間的最大值小于模的話， 就不用繼續向葉子更新了。然后其他的大于模的就更新到葉子節點。
然后對于NicoNumber來說，只有6，2的冪次和素數來說是符合的。所以可以預處理出來。然后就可以用線段樹來維護了。
代碼如下：

#include <iostream> #include <string.h> #include <math.h> #include <queue> #include <algorithm> #include <stdlib.h> #include <map> #include <set> #include <stdio.h> #include <time.h> using namespace std; #define LL long long #define pi acos(-1.0) #pragma comment(linker, "/STACK:1024000000") #define root 1, n, 1 #define lson l, mid, rt<<1 #define rson mid+1, r, rt<<1|1 const int mod=1e9+7; const int INF=0x3f3f3f3f; const double eqs=1e-9; const int MAXN=100000+10; bool isprime[MAXN*100], ok[MAXN*100]; int prime[MAXN*10]; int Max[MAXN<<2], sum[MAXN<<2]; void init() {int tot=0, i, j;ok[0]=ok[1]=1;ok[6]=1;for(i=2;i<=10000000;i++){if(!isprime[i]) {prime[tot++]=i;ok[i]=true;}for(j=0;j<tot;j++){if(i*prime[j]>10000000) break;isprime[i*prime[j]]=true;if(i%prime[j]==0) break;}}int x=2;while(x<=10000000){ok[x]=true;x<<=1;} } void PushUp(int rt) {Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void Build(int l, int r, int rt) {if(l==r){scanf("%d",&Max[rt]);sum[rt]=ok[Max[rt]];return ;}int mid=l+r>>1;Build(lson);Build(rson);PushUp(rt); } void Update1(int p, int x, int l, int r, int rt) {if(l==r){Max[rt]=x;sum[rt]=ok[x];return ;}int mid=l+r>>1;if(p<=mid) Update1(p,x,lson);else Update1(p,x,rson);PushUp(rt); } void Update2(int ll, int rr, int x, int l, int r, int rt) {if(ll<=l&&rr>=r){if(Max[rt]<x) return ;}if(l==r){Max[rt]%=x;sum[rt]=ok[Max[rt]];return ;}int mid=l+r>>1;if(ll<=mid) Update2(ll,rr,x,lson);if(rr>mid) Update2(ll,rr,x,rson);PushUp(rt); } int Query(int ll, int rr, int l, int r, int rt) {if(ll<=l&&rr>=r){return sum[rt];}int mid=l+r>>1, ans=0;if(ll<=mid) ans+=Query(ll,rr,lson);if(rr>mid) ans+=Query(ll,rr,rson);return ans; } int main() {int n, i, j, l, r, p, v, q, x;init();while(scanf("%d",&n)!=EOF){memset(Max,0,sizeof(Max));memset(sum,0,sizeof(sum));Build(root);scanf("%d",&q);while(q--){scanf("%d",&x);if(x==1){scanf("%d%d",&l,&r);printf("%d\n",Query(l,r,root));}else if(x==2){scanf("%d%d%d",&l,&r,&v);Update2(l,r,v,root);}else{scanf("%d%d",&p,&v);Update1(p,v,root);}}}return 0; }

總結

以上是生活随笔為你收集整理的ZOJ 3886 Nico Number (线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。