C++14(g++5.4) 解法, 执行用时: 594ms, 内存消耗: 12516K, 提交时间: 2018-06-13 12:33:37

#include<bits/stdc++.h>
#define exe(x) (x)*((x)-1)/2
using namespace std;
typedef long long LL;
const int N = 300000+5;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int ans[N],Ans,cnt1[N],cnt2[N],zero;
int ar[N],n,belong[N],num[N];
struct lp{
	int l,r,id;
}op[N];
bool cmp(lp &a, lp &b){
	if(belong[a.l]==belong[b.l])return a.r<b.r;
	return belong[a.l]<belong[b.l];
}
int ab(int x){
	return x<0?-x:x;
}
void add(int x,int f){
	if(ar[x]==0)zero+=f;
	else if(ar[x]>0){
		Ans-=exe(cnt1[ar[x]]);
		cnt1[ar[x]]+=f;
		Ans+=exe(cnt1[ar[x]]);
	}else{
		Ans-=exe(cnt2[ar[x]]);
		cnt2[ar[x]]+=f;
		Ans+=exe(cnt2[ar[x]]);
	}
}
int main(int argc, char const *argv[]){
	while(~scanf("%d",&n)){
		int sz=sqrt(1.0*n);
		for(int i=1;i<=n;++i){
			scanf("%d",&ar[i]);
			belong[i]=(i-1)/sz+1;
			for(int j=2;j*j<=ab(ar[i]);++j){
				while(ar[i]%(j*j)==0)ar[i]/=(j*j);
			}
		}
		int q;
		scanf("%d",&q);
		for(int i=0;i<q;++i){
			scanf("%d%d",&op[i].l,&op[i].r);
			op[i].id=i;
		}
		sort(op,op+q,cmp);
		memset(cnt1,0,sizeof(cnt1));
		memset(cnt2,0,sizeof(cnt2));
		int L=1,R=0;Ans=zero=0;
		for(int i=0;i<q;++i){
			while(L<op[i].l)add(L++,-1);
			while(L>op[i].l)add(--L,1);
			while(R<op[i].r)add(++R,1);
			while(R>op[i].r)add(R--,-1);
			ans[op[i].id]=Ans+zero*(op[i].r-op[i].l)-exe(zero);
		}
		for(int i=0;i<q;++i){
			printf("%d\n",ans[i] );
		}
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 738ms, 内存消耗: 16092K, 提交时间: 2018-06-05 21:42:26

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1e6+88;
int l,r,zero,pos[N],A[N],P[N],cnt1[N],cnt2[N],ans[N],Ans;
struct node{
	int l,r,id;
	bool operator < (const node &A){
		return pos[l]==pos[A.l]?r<A.r:pos[l]<pos[A.l];
	}
}Q[N];
void init(){
	for(int i=1;i<=1000000;++i) P[i]=i;
	for(int i=2;i<=1000000;++i) {
		if(P[i]==i) {
			for(int j=i<<1;j<=1000000;j+=i) {
				while(P[j]%(i*i)==0) P[j]/=i*i;
			}
		}
	}
}
int calc(int x){
	return x*(x-1)/2;
}
void work(int x,int f){
	if(A[x]==0) zero+=f;
	else if(A[x]>0) {
		Ans-=calc(cnt1[P[A[x]]]);
		cnt1[P[A[x]]]+=f;
		Ans+=calc(cnt1[P[A[x]]]);
	}
	else {
		Ans-=calc(cnt2[P[A[x]]]);
		cnt2[P[A[x]]]+=f;
		Ans+=calc(cnt2[P[A[x]]]);
	}
}
int main(){
	int m,n,block;
	init();
	scanf("%d",&n);
	block=(int)sqrt(n);
	for(int i=1;i<=1000000;++i) pos[i]=i/block;
	for(int i=1;i<=n;++i) scanf("%d",A+i);
	scanf("%d",&m);
	for(int i=1;i<=m;++i) scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id=i;
	sort(Q+1,Q+m+1);
	l=1,r=0;
	for(int i=1;i<=m;++i) {
		while(l<Q[i].l) work(l,-1),++l;
		while(l>Q[i].l) --l,work(l,1);
		while(r>Q[i].r) work(r,-1),--r;
		while(r<Q[i].r) ++r,work(r,1);
		ans[Q[i].id]=Ans+zero*(r-l)-calc(zero);
	}
	for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
}