P1494 [国家集训队]小Z的袜子
莫队第一题，板子题
P1494[国家集训队]小Z的袜子
大致题意：
有一个人叫小z，他想在一堆标好了号的袜子里找可以组成多少对颜色相同的袜子；
题解：
最简单的思想是将区间以l为优先级，r为次级排序，用以前已经做过的结果转移当前，时间复杂度（每次）是
| l - l(pre) |+| r - r(pre) |
而莫队的分块思想就是为将这个时间复杂度降到最低，就是把上面这个式子的值降到最小，通常是分成sqrt(n)块，具体看程序旁批
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#define N 50010
#define ll long long
using namespace std;
inline int getint(){
int w=0;bool f=false;char c=getchar();
while((c<'0'||c>'9')&&c!='-')c=getchar();
if(c=='-')f=true,c=getchar();
while(c>='0'&&c<='9')w=w*10+c-'0',c=getchar();
return f?-w:w;
}
int n,m,c[N],k;
ll cnt[N];
struct ono{
int num,l,r;
}q[N];
struct an{
ll fiz,fim;
}ans[N];
inline bool cmp(ono x,ono y){
if(x.l/k==y.l/k)return x.r<y.r;
// if(x.l/k==y.l/k&&x.r<y.r)return true;这样可能会在后面if(x.l<y.l)时也换一次导致错误；
if(x.l<y.l)return true;
return false;
//if(x.l<y.l)return true;
//else if(x.l==y.l&&x.r<y.r)return true;
//return false;
}
inline ll gcd(int x,int y){return y?gcd(y,x%y):x;}
int main()
{
n=getint();m=getint();k=sqrt(n-1)+1;
for(register int i=0;i<n;i++)c[i]=getint();
for(register int i=0;i<m;i++) q[i].l=getint()-1,q[i].r=getint()-1,q[i].num=i;
sort(q,q+m,cmp);
int ri=-1,li=0;
ll fz=0,fm,g,mid;
for(register int i=0;i<m;i++){
while(ri<q[i].r)fz+=cnt[c[++ri]]++;//r从-1开始，就先++；
while(li>q[i].l)fz+=cnt[c[--li]]++;
//因为要两只一样的袜子才能成一双，所以要先+在fz上再cnt++（e.g:当有第二只袜子出现时就先fz+1表示有了一双，再cnt++，表示有多少只袜子；
//因为是任意两只袜子组成一对，所以新进的袜子可以和cnt中任意一只组合，所以直接加cnt；
while(ri>q[i].r)fz-=--cnt[c[ri--]];//以前算过，先算后-；
while(li<q[i].l)fz-=--cnt[c[li++]];
//当有三只袜子时，实际是两对，所以先减cnt，再减fz；
fm=1ll*(q[i].r-q[i].l+1)*(q[i].r-q[i].l)>>1;//组合；
mid=fz;//要gcd（fz，fm），而又要再次用到fz，所以用一个mid
if(fm==0||fz==0){ans[q[i].num].fiz=0;ans[q[i].num].fim=1;continue;}
g=gcd(fm,fz);fm/=g;mid/=g;ans[q[i].num].fiz=mid;ans[q[i].num].fim=fm;
}
for(register int i=0;i<m;i++)printf("%lld/%lld\n",ans[i].fiz,ans[i].fim);
return 0;
}