TLE#6求助

#include<bits/stdc++.h>
using namespace std;
int in(){
    int k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
void out(int x){
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else out(x/10),putchar(x%10+'0');
}
int n,q,b[200005],k,l=1,r,ans,vis[1000006],cnt[200005];
struct Q{
	int l,r,k,id;
}a[200005];
bool cmp(Q x,Q y){
	if(x.k!=y.k) return x.k<y.k;
	if(x.k%2==0) return x.r>y.r;
	return x.r<y.r;
}
int main(){
	n=in(),q=in();
	k=n/sqrt(q*2/3)+1;
	for(int i=1;i<=n;i++) b[i]=in();
	for(int i=1;i<=q;i++) a[i].l=in(),a[i].r=in(),a[i].k=i/k,a[i].id=i;
	sort(a+1,a+1+q,cmp);
	for(int i=1;i<=q;i++){
		while(l<a[i].l) ans+=(1-2*vis[b[l]])*b[l],vis[b[l]]--,l++;
		while(r<a[i].r)	r++,ans+=(1+2*vis[b[r]])*b[r],vis[b[r]]++;
		while(l>a[i].l)	l--,ans+=(1+2*vis[b[l]])*b[l],vis[b[l]]++;
		while(r>a[i].r)	ans+=(1-2*vis[b[r]])*b[r],vis[b[r]]--,r--;
		cnt[a[i].id]=ans;
	}
	for(int i=1;i<=q;i++) out(cnt[i]),printf("\n");
	return 0;
}
/*
a*a->(a+1)*(a+1)=a*a+1+2*a
a*a->(a-1)*(a-1)=a*a+1-2*a
*/