在 $[30,79]$ pts 之间波动，心态炸了

#pragma GCC target("avx")
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#define RI register int
#define for_dir_i for(j=hd[a[i]];j&&pf[dv[j]]<a[i];j=nt[j])
using namespace std;
const int N=5e5+11; 
int fk[N],m1,m,a[N],d[N],n,mx,sq1,f[N],c[N],k,s=0;
long long ans1[N],ans[N],ans2[N],pf[N],e[N],c1[N];
int g[N],dv[20*N],m2,hd[N],nw[N],nt[20*N];
struct qw{int l,r,num;}q[N];
struct qw1{int num,l,r,p,st;}b[N<<1];
bool mo(qw x,qw y)
	{if(fk[x.l]==fk[y.l])return fk[x.l]&1?x.r<y.r:x.r>y.r;
	return x.l<y.l;}
bool s1(qw1 x,qw1 y){return x.p<y.p;}
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline void addln(int x,int y){
	nt[++m2]=hd[x],dv[m2]=y,hd[x]=m2;}
inline int minn(int x,int y){return x<y?x:y;}
inline int maxx(int x,int y){return x>y?x:y;}
inline int rd(){
	int i=0;char c=getc();
	while(c<48||c>57)c=getc();printf("%c\n",c);
	while(c>47&&c<58)i=(i<<3)+(i<<1)+c-48,c=getc();
	return i;}
inline void mt(){
	RI i,j,lpt=1,rpt=0;
	for(i=1;i<=m;i++){ 
		if(rpt<q[i].r)
			{b[++m1]={i,rpt+1,q[i].r,lpt-1,-1};
			ans[i]+=e[q[i].r]-e[rpt];rpt=q[i].r;}
		if(lpt>q[i].l)
			{b[++m1]={i,q[i].l,lpt-1,rpt,1};
			ans[i]-=e[lpt-1]-e[q[i].l-1];lpt=q[i].l;}
		if(rpt>q[i].r)
			{b[++m1]={i,q[i].r+1,rpt,lpt-1,1};
			ans[i]+=e[q[i].r]-e[rpt];rpt=q[i].r;}
		if(lpt<q[i].l)
			{b[++m1]={i,lpt,q[i].l-1,rpt,-1};
			ans[i]-=e[lpt-1]-e[q[i].l-1];lpt=q[i].l;}}
}//莫队 
inline void sole(){
	RI i,j,j1,sq=n/sqrt(m)+1;
	for(i=1;i<=n;i++){j1=0;
		e[i]+=e[i-1]+1;e[i]+=d[a[i]];
		for_dir_i{
			d[dv[j]]++;d[a[i]/dv[j]]++;
		}if(pf[dv[j]]==a[i])d[dv[j]]++;j1=0;
		for_dir_i
			e[i]+=c[dv[j]],j1+=c[a[i]/dv[j]];e[i]+=j1;
		if(pf[dv[j]]==a[i])e[i]+=c[dv[j]];
		fk[i]=(i-1)/sq+1;c[a[i]]++;}
} 
inline void solf1(){
	RI i,j,h,j1,u;register long long v;
	h=0;while(!b[++h].p);h--;
	for(i=1,c[0]=0;i<=n;++i)
		c[i]=a[i]>sq1?c[i-1]+1:c[i-1];
	for(i=1;i<=n;++i,--h){
		for_dir_i
			f[dv[j]]++,f[a[i]/dv[j]]++;
		if(pf[dv[j]]==a[i])f[dv[j]]++;
		if(a[i]>sq1){
			for(j=j1=a[i];j<=mx;j+=j1)f[j]++;
		}while(b[++h].p==i){v=0;
			for(j=b[h].l;j<=b[h].r;j++)v+=f[a[j]];
			ans[b[h].num]+=v*b[h].st;}
	}
}
inline void sdsq(){
	RI i,j=sqrt(mx),h=1e9;
	for(i=1,c1[0]=0;i<=n;i++)c1[a[i]]+=mx/a[i];
	for(i=mx-1;i;i--)c1[i]+=c1[i+1];
	for(i=1;i<=j;i++){
		if(c1[i+1]+n*i*5<h)
			sq1=i,h=c1[i+1]+n*i*5;}
}//手动找阈值 
int main()
{	
	RI h=0,i,j,u,sq,j1,sq2,w;n=rd(),m=rd(),mx=-1;
	register long long v;
	for(i=1,h=0;i<=n;i++)
		a[i]=rd(),mx=maxx(mx,a[i]);
	for(i=mx;i;i--)
		for(j=i,pf[i]=1ll*i*i;j<=mx;j+=i)addln(j,i);
	sole();
	sdsq();
	for(i=1;i<=m;i++)
		q[i].num=i,q[i].l=rd(),q[i].r=rd();
	sort(q+1,q+m+1,mo);
	mt();
	sort(b+1,b+m1+1,s1);
	b[m1+1].p=-1; solf1();
	for(i=1;i<=mx;i++)nw[i]=hd[i];
	for(j=1;j<=sq1;++j){
		for(i=1,g[0]=c[0]=0;i<=n;i++)
			g[i]=(dv[nw[a[i]]]==j)+g[i-1],c[i]=(a[i]==j)+c[i-1];
		h=0;
		while(!b[++h].p);h--;
		for(i=1;i<=n;++i,--h){
			if(dv[nw[i]]==j)nw[i]=nt[nw[i]];
			while(b[++h].p==i)
				ans[b[h].num]+=b[h].st>0?1ll*(g[b[h].r]-g[b[h].l-1])*c[i]:1ll*(g[b[h].l-1]-g[b[h].r])*c[i];}
	}for(i=1,v=0;i<=m;i++)
		ans[i]+=ans[i-1],ans1[q[i].num]=ans[i];
	for(i=1;i<=m;i++)printf("%lld\n",ans1[i]);
	return 0;
}