题目大意：
给定n个数
m个询问 询问l r区间内的孤独数的个数
孤独数的定义为在该区间内与其他所有数互质的数
看注释
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+;
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=;
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,,sizeof(isprime));
for(int i=;i<N;i++)
if(isprime[i]){
for(int j=i;j<N;j+=i)
isprime[j]=, vec[j].push_back(i);
}
}// 筛出质数表 vec[j]内为j的所有质因子
int main()
{
prime();
while(~scanf("%d%d",&n,&m)) {
memset(T,,sizeof(T));
memset(cur,,sizeof(cur));
for(int i=;i<=n;i++) {
int x; scanf("%d",&x);
a[i].l=, a[i].r=n+, a[i].id=i;
// 第i个数的最大互质区间为开区间(l,r)
for(int j=;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=;i<=m;i++)
scanf("%d%d",&q[i].l,&q[i].r), q[i].id=i;
sort(a+,a++n,cmp);
sort(q+,q++m,cmp);
priority_queue <NODE> que; // 保存树状数组维护的数 并按位置从小到大排
for(int i=,j=;i<=m;i++) {
// 若树状数组维护的区间中
// 有位置不包含在当前查询区间内部的 应该先清除
while(!que.empty() && que.top().id<q[i].l) {
addT(que.top().id,-);
addT(que.top().r,);
que.pop();
}
// 若有互质区间左端超过查询区间的左端
// 则有可能是查询区间内的孤独数 加入树状数组
while(j<=n && a[j].l<q[i].l) {
addT(a[j].id,);
addT(a[j].r,-); // 将该数所在的位置到其互质区间的右端加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=;i<=m;i++)
printf("%d\n",ans[i]);
} return ;
}