rt 吸了氧最后两个点还是超时

但是我不想用离散化

有希望卡过去吗

#include<bits/stdc++.h>
using namespace std;
int fr(){
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
	return x;
}
int n,m,mod,cur,a[500005],fk[500005];
unordered_map<int,int> np;
struct Query{
	int dx,dxl,dy,id,ans;
}q[500005];
bool cmp1(Query a,Query b){
	if(a.dxl!=b.dxl)return a.dxl<b.dxl;
	if(a.dxl&1)return a.dy<b.dy;
	return a.dy>b.dy;
}
bool cmp2(Query a,Query b){
	return a.id<b.id;
}
void add(int p){
	np[a[p]]++;
	if(np[a[p]]==2)cur++;
	if(np[a[p]]==3)cur--;
}
void del(int p){
	np[a[p]]--;
	if(np[a[p]]==2)cur++;
	if(np[a[p]]==1)cur--;
}
int main(){
	n=fr(),m=fr();
	mod=sqrt(n);
	for(int i=1;i<=n;i++){
		fk[i]=(i-1)/mod;
		a[i]=fr();
	}
	for(int i=1;i<=m;i++){
		q[i].dx=fr(),q[i].dy=fr();
		q[i].id=i,q[i].dxl=fk[q[i].dx];
	}
	sort(q+1,q+m+1,cmp1);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		while(q[i].dx<l)add(--l);
		while(q[i].dx>l)del(l++);
		while(q[i].dy<r)del(r--);
		while(q[i].dy>r)add(++r);
		q[i].ans=cur;
	}
	sort(q+1,q+m+1,cmp2);
	for(int i=1;i<=m;i++)
		printf("%d\n",q[i].ans);
	return 0;
}