不知道怎么T了后面4个点

#include<bits/stdc++.h>

using namespace std;

int n,m,wnm[50005],bkt[50005];

struct waz{
	int l;
	int r;
	int num;
}wz[50005];

struct as{
	int fz;
	int fm;
}ans[50005];

inline int c2(int x){
	return x*(x-1)/2;
}

inline bool cmp(waz x,waz y){
	if(x.l/sqrt(n)!=y.l/sqrt(n)){
		return x.l/sqrt(n)<y.l/sqrt(n);
	}else{
		return x.r<y.r;
	}
}

inline int gcd(int x,int y){return !y?x:gcd(y,x%y);}

int main(){
//	freopen("P1494_4.in","r",stdin);
//	freopen("emmm.out","w",stdout);
	register int i,j,k,p,q,hd,tl;
	as ass;
	
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++){
		scanf("%d",&wnm[i]);
	}
	for(i=1;i<=m;i++){
		scanf("%d %d",&p,&q);
		wz[i].l=p;
		wz[i].r=q;
		wz[i].num=i;
	}
	sort(wz+1,wz+m+1,cmp);
	hd=0;
	tl=0;
	for(i=1;i<=m;i++){
		if(wz[i].l==wz[i].r){
			ans[wz[i].num].fz=0;
			ans[wz[i].num].fm=1;
			continue;
		}
		if(hd==0&&tl==0){
			hd=wz[i].l;
			tl=wz[i].r;
			for(j=hd;j<=tl;j++){
				bkt[wnm[j]]++;
			}
			ass.fz=0;
			for(j=1;j<=n;j++){
				if(bkt[j]){
					ass.fz+=c2(bkt[j]);
				}
			}
			ass.fm=c2(wz[i].r-wz[i].l+1);
			ans[wz[i].num]=ass;
			continue;
		}
		if(hd<wz[i].l){
			for(j=hd;j<=wz[i].l-1;j++){
				ass.fz-=c2(bkt[wnm[j]]);
				bkt[wnm[j]]--;
				ass.fz+=c2(bkt[wnm[j]]);
				ass.fm=c2(tl-j);
			}
			hd=wz[i].l;
		}
		if(tl<wz[i].r){
			for(j=tl+1;j<=wz[i].r;j++){
				ass.fz-=c2(bkt[wnm[j]]);
				bkt[wnm[j]]++;
				ass.fz+=c2(bkt[wnm[j]]);
				ass.fm=c2(j-hd+1);
			}
			tl=wz[i].r;
		}
		if(hd>wz[i].l){
			for(j=hd-1;j>=wz[i].l;j--){
				ass.fz-=c2(bkt[wnm[j]]);
				bkt[wnm[j]]++;
				ass.fz+=c2(bkt[wnm[j]]);
				ass.fm=c2(tl-j+1);
			}
			hd=wz[i].l;
		}
		if(tl>wz[i].r){
			for(j=tl;j>=wz[i].r+1;j--){
				ass.fz-=c2(bkt[wnm[j]]);
				bkt[wnm[j]]--;
				ass.fz+=c2(bkt[wnm[j]]);
				ass.fm=c2(j-hd);
			}
			tl=wz[i].r;
		}
		ans[wz[i].num]=ass;
	}
	for(i=1;i<=m;i++){
		printf("%d/%d\n",ans[i].fz/gcd(ans[i].fz,ans[i].fm),ans[i].fm/gcd(ans[i].fz,ans[i].fm));
	}
	
	return 0;
}

看了很多题解，感觉复杂度没太大区别 淦 ;w;