C112 莫队算法 P1494 [国家集训队] 小 Z 的袜子

视频链接：

Luogu P1494 [国家集训队] 小 Z 的袜子

// 普通莫队 O(n*sqrt(n))
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N=50005;
int n,m,B,a[N];
int sum,cnt[N],ans1[N],ans2[N];
struct Q{
  int l,r,id;
  //按l所在块的编号l/B和r排序
  bool operator<(const Q &x) const{
    if(l/B!=x.l/B) return l<x.l;
    if((l/B)&1) return r<x.r;
    return r>x.r;
  }
}q[N];

void add(int x){
  sum+=cnt[x]; //当前x与前面每个x组合成双
  cnt[x]++;    //x的出现次数
}
void del(int x){
  cnt[x]--; 
  sum-=cnt[x];
}
int gcd(int a,int b){
  return b?gcd(b,a%b):a;
}
int main(){
  scanf("%d%d",&n,&m);
  B=sqrt(n); //块的大小
  for(int i=1;i<=n;i++) //颜色
    scanf("%d",&a[i]);
  for(int i=1;i<=m;i++) //询问
    scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
  sort(q+1,q+m+1);
  for(int i=1,l=1,r=0;i<=m;i++){
    if(q[i].l==q[i].r){
      ans1[q[i].id]=0,ans2[q[i].id]=1;
      continue;
    }
    while(l>q[i].l)add(a[--l]);//左扩展
    while(r<q[i].r)add(a[++r]);//右扩展
    while(l<q[i].l)del(a[l++]);//左删除
    while(r>q[i].r)del(a[r--]);//右删除
    ans1[q[i].id]=sum;
    ans2[q[i].id]=1ll*(r-l+1)*(r-l)/2;
  }
  for(int i=1;i<=m;i++){
    if(ans1[i]){
      int g=gcd(ans1[i],ans2[i]);
      ans1[i]/=g,ans2[i]/=g; //最简分数
    }
    else ans2[i]=1;
    printf("%d/%d\n",ans1[i],ans2[i]);
  }
}