题目大意:
给定n个数
m个询问 询问l r区间内的孤独数的个数
孤独数的定义为在该区间内与其他所有数互质的数
看注释
#include <bits/stdc++.h> using namespace std; const int N=1e5+5; struct NODE { int l,r,id; bool operator <(const NODE& p)const { return id>p.id; } }a[N], q[N]; bool cmp(NODE& p,NODE& q) { return p.l<q.l; } int T[N]; void addT(int i,int x) { while(i<=N) { T[i]+=x; i+=-i&i; } } int sum(int i) { int res=0; while(i) { res+=T[i]; i-=-i&i; } return res; } int n,m,cur[N],ans[N]; vector <int> vec[N]; bool isprime[N]; void prime() { memset(isprime,1,sizeof(isprime)); for(int i=2;i<N;i++) if(isprime[i]){ for(int j=i;j<N;j+=i) isprime[j]=0, vec[j].push_back(i); } }// 筛出质数表 vec[j]内为j的所有质因子 int main() { prime(); while(~scanf("%d%d",&n,&m)) { memset(T,0,sizeof(T)); memset(cur,0,sizeof(cur)); for(int i=1;i<=n;i++) { int x; scanf("%d",&x); a[i].l=0, a[i].r=n+1, a[i].id=i; // 第i个数的最大互质区间为开区间(l,r) for(int j=0;j<vec[x].size();j++){ int t=vec[x][j]; if(cur[t]) {// cur[t]为上一个以t为质因子的数的位置 a[i].l=max(a[i].l,cur[t]); a[cur[t]].r=min(a[cur[t]].r,a[i].id); } // 处理第i个数x的最大互质区间 cur[t]=a[i].id; // 更新cur[t] } } for(int i=1;i<=m;i++) scanf("%d%d",&q[i].l,&q[i].r), q[i].id=i; sort(a+1,a+1+n,cmp); sort(q+1,q+1+m,cmp); priority_queue <NODE> que; // 保存树状数组维护的数 并按位置从小到大排 for(int i=1,j=1;i<=m;i++) { // 若树状数组维护的区间中 // 有位置不包含在当前查询区间内部的 应该先清除 while(!que.empty() && que.top().id<q[i].l) { addT(que.top().id,-1); addT(que.top().r,1); que.pop(); } // 若有互质区间左端超过查询区间的左端 // 则有可能是查询区间内的孤独数 加入树状数组 while(j<=n && a[j].l<q[i].l) { addT(a[j].id,1); addT(a[j].r,-1); // 将该数所在的位置到其互质区间的右端加1 que.push((NODE){a[j].l,a[j].r,a[j].id}); j++; } ans[q[i].id]=sum(q[i].r); // 第一个while()已经排除了位置在查询区间左端外的那些数 // 即此时sum(q[i].l-1)必等于0 所以不需要减去它 // 直接取查询区间右端的前缀和就可以了 } for(int i=1;i<=m;i++) printf("%d\n",ans[i]); } return 0; }