记录编号	147660	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2010] 小Z的袜子	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	2.647 s
提交时间	2015-02-02 21:15:18	内存使用	2.41 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=0x3fffffff;
//==============struct declaration==============
int pos[50010];
struct query{
  int l,r;
  bool operator <(const query &rhs) const{
    return pos[l]<pos[rhs.l]||(pos[l]==pos[rhs.l]&&pos[r]<pos[rhs.r]);
  }
};
//==============var declaration=================
const int MAXN=50010;
int n,m,block_size;
int sock[MAXN],rk[MAXN];
long long color[MAXN];
long long up[MAXN],down[MAXN];
query Query[MAXN];
//==============function declaration============
bool cmp(int a,int b){return Query[a]<Query[b];}
long long gcd(long long a,long long b){return a%b==0?b:gcd(b,a%b);}
//==============main code=======================
int main()
{  
#define FILE__
#ifdef FILE__
  freopen("hose.in","r",stdin);
  freopen("hose.out","w",stdout);
#endif  
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++)
    scanf("%d",sock+i);
  for(int i=1;i<=m;i++){
    rk[i]=i;
    scanf("%lld%lld",&Query[i].l,&Query[i].r);
  }
  block_size=int(sqrt(n+.0));
  for(int i=1;i<=n;i++)
    pos[i]=i/block_size;
  sort(rk+1,rk+1+m,cmp);
  int l=1,r=1;color[sock[1]]++;
  //double start_t=clock();
  for(int i=1;i<=m;i++){
    query &Q=Query[rk[i]];
    up[rk[i]]=up[rk[i-1]];
    while (l<Q.l){
      up[rk[i]]-=color[sock[l]]*(color[sock[l]]-1);
      color[sock[l]]--;
      up[rk[i]]+=(color[sock[l]])*(color[sock[l]]-1);
      l++;
    }
    while (l>Q.l){
      l--;
      up[rk[i]]-=color[sock[l]]*(color[sock[l]]-1);
      color[sock[l]]++;
      up[rk[i]]+=(color[sock[l]])*(color[sock[l]]-1);
      
    }
    while (r<Q.r){
      r++;
      up[rk[i]]-=color[sock[r]]*(color[sock[r]]-1);
      color[sock[r]]++;
      up[rk[i]]+=(color[sock[r]])*(color[sock[r]]-1);
    }
    while (r>Q.r){
      up[rk[i]]-=color[sock[r]]*(color[sock[r]]-1);
      color[sock[r]]--;
      up[rk[i]]+=(color[sock[r]])*(color[sock[r]]-1);
      r--;
    }
    down[rk[i]]=(long long)(Q.r-Q.l)*(Q.r-Q.l+1);
    //double end_t=clock();
    //printf("Quert No.%d :%.6lf\n",i,(end_t-start_t)/CLOCKS_PER_SEC);
  }
  for(int i=1;i<=m;i++){
    if (up[i]!=0){
      long long G=gcd(up[i],down[i]);
      //cout<<up[i]<<" "<<down[i]<<" "<<G<<endl;
      //cout<<i<<" ";
      printf("%lld/%lld\n",up[i]/G,down[i]/G);
    }
    else
      printf("0/1\n");
  }
  return 0;
}
//================fuction code====================