分析：找到每一個點的左邊離他最近的不互質數，記錄下標(L數組)，右邊一樣如此（R數組），預處理

????????這個過程需要分解質因數O（n*sqrt(n))

??????? 然后離線，按照區間右端點排序

??????? 然后掃一遍，對于當前拍好順序的第i個詢問，將所有小于r的點加入更新

??????? 更新的過程是這樣的

?????? （1）對于剛加入點x，樹狀數組L[x]位置+1? ?把這個定義為左更新

???????（2）對于所有R[i]=x的點，樹狀數組L[i]位置-1，i位置+1?? 把這個定義為右更新

?????? （3）查詢是詢問區間 l->r的和

?

?????? 時間復雜度分析，因為每個點左更新，右更新各一次，所以單組測試用例是O（nlogn)的

?

?????? 下面來解釋為啥這樣更新

?????? 查看當前詢問 l , r,對于所有小于 l 的點 i，它的所有更新（左更新和右更新）不會影響到樹狀數組區間 l 到 r 的 和

?????? 對于在l,r區間的點 i，如果 R[i]<=r,那么對于區間 l ->r 有 1 的貢獻

?????????????????????????????????? 如果 R[i]>r,對于這個點，只有左更新L[i]+1;

????????????????????????????????????????????????????如果 L[i]>=l ，對于查詢區間有 1 的貢獻

??????????????????????????????????????????????????? 如果 L[i]<l，對于查詢區間沒有貢獻

???????不難發現，這樣對于查詢區間有貢獻的點，都是會和別人打架的點

?????? 所以該查詢的答案就是? 查詢區間長度 - 樹狀數組區間和

?????? 然后以下看代碼

????

#include<cstdio> #include<cstring> #include<queue> #include<cstdlib> #include<algorithm> #include<vector> #include<cmath> using namespace std; typedef long long LL; const int N=2e5; const LL mod=1e9+7; int a[N+5],c[N+5]; int f[N+5],h[N+5],k[N+5]; vector<int>g[N+5]; vector<int>b[N+5]; struct Que {int l,r,id;bool operator<(const Que &e)const{return r<e.r;} }q[N+5]; int n,m; bool vis[N+5]; int prime[N+5],cnt,res[N+5]; void add(int x,int t) {for(;x<=n+1;x+=(x&(-x)))c[x]+=t; } int get(int x) {int ans=0;for(;x>0;x-=(x&(-x)))ans+=c[x];return ans; } int main() {for(int i=2; i*i<=N; ++i){if(vis[i])continue;for(int j=i*i; j<=N; j+=i)vis[j]=1;}for(int i=2; i<=N; ++i)if(!vis[i])prime[cnt++]=i;for(int i=2; i<=N; ++i){int t=i;for(int j=0; j<cnt&&prime[j]*prime[j]<=i; ++j){if(t%prime[j])continue;g[i].push_back(prime[j]);while(t%prime[j]==0)t/=prime[j];if(t==1)break;}if(!vis[t]&&t!=1)g[i].push_back(t);}while(~scanf("%d%d",&n,&m),n){memset(f,0,sizeof(f));memset(c,0,sizeof(c));for(int i=2; i<=n+1; ++i){scanf("%d",&a[i]);h[i]=1;k[i]=n+2;}for(int i=2; i<=n+1; ++i){for(int j=0; j<g[a[i]].size(); ++j){int x=g[a[i]][j];h[i]=max(h[i],f[x]);f[x]=i;}}for(int i=1; i<=N; ++i)f[i]=n+2;for(int i=n+1; i>1; --i){for(int j=0; j<g[a[i]].size(); ++j){int x=g[a[i]][j];k[i]=min(k[i],f[x]);f[x]=i;}}for(int i=1;i<=m;++i)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;sort(q+1,q+1+m);for(int i=1;i<=n;++i)b[i].clear();for(int i=2;i<=n+1;++i)b[k[i]].push_back(i);int x=2;for(int i=1;i<=m;++i){while(x<=n+1&&x<=q[i].r+1){add(h[x],1);for(int j=0;j<b[x].size();++j){int y=b[x][j];add(h[y],-1);add(y,1);}++x;}int t=get(q[i].r+1)-get(q[i].l);res[q[i].id]=q[i].r-q[i].l+1-t;}for(int i=1;i<=m;++i)printf("%d\n",res[i]);}return 0; } View Code

?

轉載于:https://www.cnblogs.com/shuguangzw/p/5272595.html

總結

以上是生活随笔為你收集整理的HDU 4777 Rabbit Kingdom 树状数组的全部內容，希望文章能夠幫你解決所遇到的問題。

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