样例都没过

#include<bits/stdc++.h>
using namespace std;
int t,n,m;
int a[100010];
int pos[100010];
struct Q{
	int l,r,x;
}q[100010];
bool cmp(Q x,Q y){
    if(pos[x.l]==pos[y.l]){
        return x.r<y.r;
    }else{
        return x.l<y.l;
    }
}
int res;
map<int,int> cnt;
void add(int k){
	cnt[a[k]]++;
	res+=cnt[a[k]]-(cnt[a[k]]-1);
}
void sub(int k){
	cnt[a[k]]--;
	res-=((cnt[a[k]]+1)-cnt[a[k]]);
}
int main(){
	scanf("%d",&t);
	while(t--){
		res=0;
		cnt.clear();
		for(int i=1;i<=n;i++){
			pos[i]=0;
		}
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		scanf("%d",&m);
		for(int i=1;i<=m;i++){
			scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].x);
		}
		sort(q+1,q+1+m,cmp);
		int siz=sqrt(n);
		for(int i=1;i<=n;i++){
			pos[i]=i/siz;
		}
	    int l=1,r=0;
	    for(int i=1;i<=m;i++){
	        while(q[i].l<l) add(--l);
	        while(q[i].r>r) add(++r);
	        while(q[i].l>l) sub(l++);
	        while(q[i].r<r) sub(r--);
	        printf("%d\n",res);
	    }
	}
    return 0;
}