记录编号	155942	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2010] 小Z的袜子	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.896 s
提交时间	2015-04-01 08:37:50	内存使用	2.25 MiB

/****************************************\
* Author : ztx
* Title  : [bzoj] 2038: [2009国家集训队]小Z的袜子(hose)
* ALG    : 莫队分块
* CMT    : 不想再写纯正的莫队了>_<
* Time   :
\****************************************/

#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
typedef long long ll ;
int CH , NEG ;
template <typename TP>inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>inline void reads(TP& ret) {
	while (ret=getchar() , ret<'!') ;
	while (CH=getchar() , CH>'!') ;
}

#include <algorithm>
#include <cmath>

#define  maxn  50010LL
#define  maxm  50010LL

struct QUERY {
	int l , r , belong , id ;
	bool operator < (const QUERY& b) const
	{ return belong==b.belong ? r<b.r : belong<b.belong ; }
} q[maxm] ;

int n , m ;
int szblc ;
int a[maxn] = {0} , cnt[maxn] = {0} ;
bool vis[maxn] = {0} ;
ll ansnow ;
ll ans[maxn][2] = {0} ;

inline void Reverse(int p) {
	if (vis[p]) -- cnt[a[p]] , ansnow -= cnt[a[p]] ;
	else ansnow += cnt[a[p]] , ++ cnt[a[p]] ;
	vis[p] ^= 1 ;
}

ll GCD(ll x , ll y) { return y ? GCD(y,x%y) : x ; }

int main() {
int i , L , R ;
ll gcd ;
	#define READ
	#ifdef  READ
		freopen("hose.in" ,"r",stdin ) ;
		freopen("hose.out","w",stdout) ;
	#endif
	read(n) , read(m) ;
	//szblc = sqrt(n) ;
	szblc = 550;
	Rep (i,1,n) read(a[i]) ;
	Rep (i,1,m) {
		read(q[i].l) , read(q[i].r) ;
		q[i].id = i , q[i].belong = q[i].l/szblc ;
	}
	std::sort(q+1,q+m+1) ;
	L = 0 , R = 0 ;
	a[0] = 0 , cnt[0] = 1 , vis[0] = true ;
	ansnow = 0 ;
	Rep (i,1,m) {
		while (L<q[i].l) Reverse(L++) ;
		while (L>q[i].l) Reverse(--L) ;
		while (R<q[i].r) Reverse(++R) ;
		while (R>q[i].r) Reverse(R--) ;
		ans[q[i].id][0] = ansnow ;
		ans[q[i].id][1] = (ll)(R-L+1)*(R-L)>>1 ;
		if (!ansnow) ans[q[i].id][1] = 1 ;
		else {
			gcd = GCD(ans[q[i].id][0],ans[q[i].id][1]) ;
			ans[q[i].id][0] /= gcd ;
			ans[q[i].id][1] /= gcd ;
		}
	}
	Rep (i,1,m)
		printf("%lld/%lld\n", ans[i][0] , ans[i][1]) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}