RT

开了O2最后一个点过不了

求教

#include<bits/stdc++.h>
using namespace std;

int read() {
	register int x=1,ans=0;register char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') x*=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){ans=(ans<<3)+(ans<<1)+ch-48;ch=getchar();}
	return x*ans;
}

const int N=50005;
int n,m,a[N],c[N];
long long a1[N],a2[N];
int f[N],s[N],id[N];

bool cmp(int x,int y) {
	if(f[x]==f[y]) return s[x]<s[y];
	return f[x]<f[y];
} 

long long gcd(long long a,long long b) {
	long long t;
	while(b) {
		t=b;b=a%b;a=t;
	}
	return a;
} 

int main() {
//	freopen("P1494_7.in","r",stdin);
//	freopen("out.txt","w",stdout);
	n=read(); m=read(); a[0]=n+1;
	for(register int i=1;i<=n;++i) a[i]=read();
	for(register int i=1;i<=m;++i) f[id[i]=i]=read(),s[i]=read();
	sort(id+1,id+m+1,cmp);
	long long x=0,y=0,k=0;
	int p=1,q=0;
	for(register int t=1;t<=m;++t) {
		int i=id[t];
		for(;p<=f[i]-1;++p) x-=--c[a[p]];
		while(q<=s[i]-1) x+=c[a[(q++)+1]]++;
		while(q>=s[i]+1) x-=--c[a[q--]];
		y=(long long)(s[i]-f[i]+1)*(s[i]-f[i])/2;
		p=f[i]; q=s[i];
		if(x==0) { a2[i]=1; continue; }
		k=gcd(x,y);
		a1[i]=x/k; a2[i]=y/k;
	}
	for(register int i=1;i<=m;++i) {
		printf("%lld/%lld\n",a1[i],a2[i]);
	}
	return 0;
}