记录编号	147433	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2010] 小Z的袜子	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.766 s
提交时间	2015-01-31 18:27:09	内存使用	2.01 MiB

/*====================Asm.Def========================*/
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
//#include <map>
using namespace std;
template <typename T>inline void getd(T &x){
	char ch = getchar();bool neg = 0;
	while(!isdigit(ch) && ch != '-')ch = getchar();
	if(ch == '-')ch = getchar(), neg = 1;
	x = ch - '0';
	while(isdigit(ch = getchar()))x = x * 10 + ch - '0';
	if(neg)x = -x;
}
/*======================================================*/
typedef long long LL;
const int maxn = 50002;
template<typename T> T gcd(T a, T b){return !a ? b : gcd(b % a, a);}
int Seq[maxn], cnt[maxn], N, M, curL = 1, curR = 1;
LL Sum;//Sum = \sum_{i=1}^maxn x_i * (x_i - 1)(当前状况下)

struct Query{int L, R, T;LL a, b;} Q[maxn];
inline bool cmp1(const Query &a, const Query &b){return a.L < b.L;}
inline bool cmp2(const Query &a, const Query &b){return a.R < b.R;}
inline bool cmp3(const Query &a, const Query &b){return a.R > b.R;}
inline bool cmpT(const Query &a, const Query &b){return a.T < b.T;}
typedef bool(*CMP_FUNC)(const Query &, const Query &);
CMP_FUNC func[2] = {cmp2, cmp3};

inline void simpl(Query &x){
	if(!x.a){x.b = 1;return;}
	register int d = gcd(x.a, x.b);
	if(d > 1)x.a /= d, x.b /= d;
}
inline void Update(int &cnt, bool add){
	if(add){
		Sum += (cnt << 1);
		++cnt;
	}
	else{
		--cnt;
		Sum -= (cnt << 1);
	}
}
inline void CreepL(int &L0, int L){
	if(L0 == L)return;
	if(L0 < L) while(L0 < L)
		Update(cnt[Seq[L0++]], false);
	else while(L0 > L)
		Update(cnt[Seq[--L0]], true);
}
inline void CreepR(int &R0, int R){
	if(R0 == R)return;
	if(R0 < R) while(R0 < R)
		Update(cnt[Seq[++R0]], true);
	else while(R0 > R)
		Update(cnt[Seq[R0--]], false);
}
inline void solve(Query &q){//将Sum, curL, curR, cnt[]均转移到[L,R]区间
	int len;
	len = q.R + 1 - q.L;
	if(curL < q.L){
		CreepR(curR, q.R);
		CreepL(curL, q.L);
	}
	else{
		CreepL(curL, q.L);
		CreepR(curR, q.R);
	}
	q.a = Sum;
	q.b = (LL)len * (len - 1);
	simpl(q);
}

inline void init(){
	getd(N), getd(M);
	int i, B, Min = 0, Max, l = 0, r;
	Max = B = (int)(sqrt((double)M) + 0.5);
	for(i = 1;i <= N;++i)getd(Seq[i]);
	for(i = 0;i < M;++i){
		getd(Q[i].L), getd(Q[i].R);
		Q[i].T = i;
	}
	sort(Q, Q + M, cmp1);
	for(r = 0;r < M;++r)if(Q[r].L >= Max){
		Min = Max;
		Max = Min + B;
		if(l != r){
			sort(Q + l, Q + r, func[r & 1]);
			l = r;
		}
	}
	++cnt[Seq[1]];
}

inline void work(){
	for(int i = 0;i < M;++i)solve(Q[i]);
	sort(Q, Q + M, cmpT);
	#ifndef DEBUG
		#ifndef TSINSEN
			for(int i = 0;i < M;++i)printf("%lld/%lld\n", Q[i].a, Q[i].b);
		#else
			for(int i = 0;i < M;++i)printf("%I64d/%I64d\n", Q[i].a, Q[i].b);
		#endif
	#else
		for(int i = 0;i < M;++i)printf("%I64d/%I64d\n", Q[i].a, Q[i].b);
	#endif
}

int main(){
	#if defined DEBUG
	freopen("test", "r", stdin);
	//freopen("output.txt", "w", stdout);
	#else
		#ifndef ONLINE_JUDGE
			freopen("hose.in", "r", stdin);
			freopen("hose.out", "w", stdout);
		#endif
	#endif
	init();
	work();
	
	#if defined DEBUG
	printf("\n%.2lfs\n", (double)clock()/CLOCKS_PER_SEC);
	#endif
	return 0;
}