P1494

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

我们来看这种问题。

它们一般会有这样的特征，每次询问区间，支持询问，得到 $[l,r]$ 的答案后，再得到 $[l+1,r]$，$[l,r+1]$，$[l-1,r]$，$[l,r-1]$ 的代价很小，比如说这题就是 $O(1)$ 的。

然后每次我们从一个区间算到另一个区间的代价就是 $|l_i-l_{i-1}|+|r_i-r_{i-1}|$ 的。

于是我们很容易有一个想法，就是把每个区间询问转化成二维平面上的点 $(l_i,r_i)$，从一个区间算到另一个区间的代价就是两点间的曼哈顿距离。

那么我们现在的计算最小代价就是这张图上的最短哈密顿路（当然，按某种想法来说不一定需要哈密顿路，最小生成树也是可以的）。

真的去找这个哈密顿路比较困难，所以我们一般就用莫队，或者说分块方法解决这类问题。

可以证明的是，莫队的复杂度和平面最短哈密顿路的数量级下限是相同的（但我并不知道怎么证。。。）。

然后我们来看莫队的想法。

我最开始看到莫队的时候，大概了解到它是一个对询问的顺序进行分块式调整的算法，一下子就有了一种复杂度较劣的方法：

先按左端点排序，块内按右端点排序。然后对于每个块，单独计算第一个询问的答案，然后再从这个答案扩展出块内的其他答案。很容易知道，这个复杂度是 $O((n+m)\sqrt{n})$。

这个复杂度固然相当不错，但并不是真的莫队，因为我们还有更加优秀的方法。

为了方便，我们直接用最短哈密顿路的方法（只计算一个询问的答案，剩下全靠扩展）。

将询问按左端点排序，在序列上分块，左端点在一个块内的再按右端点排序。

设块的大小为 $T$，则块内每次左端点扩展的复杂度都是 $O(T)$ 的，左端点跨过块的扩展复杂度仍然是 $O(T)$ 的，容易想到总的左端点扩展复杂度是 $O(mT)$ 的。

一个块内的询问的右端点是递增的，也就是一个块内的右端点扩展复杂度是 $O(n)$ 的，跨过块扩展的复杂度仍然是 $O(n)$ 的。仍然容易想到，这个右端点扩展的总复杂度是 $O\left(n^2/T\right)$ 的。

于是我们的总复杂度是 $O(mT+{\displaystyle \frac{n^2}{T}})$ 的。

根据根号平衡（设上面两项相等列个方程），$T=n/\sqrt{m}$ 的时候最优。

此时我们的复杂度就是 $O(n\sqrt{m})$。

这题具体实现的过程中，我们知道最后的答案是：

$$Ans={\displaystyle \frac{\sum _{i=1}^{k}cnt(i)(cnt(i)-1)}{len(len-1)}}$$

其中是假设有 $k$ 种颜色，区间 $[l,r]$ 中颜色为 $i$ 的数量为 $cnt(i)$，$len$ 即为区间 $[l,r]$ 的长度。

意义就是小学组合，我们挑选的方案共有 $len(len-1)$ 种，其中对于颜色 $i$，挑中颜色相同的两个的方案有 $cnt(i)(cnt(i)-1)$。并且我们容易证明每种方案是等概率的。

然后 $O(1)$ 扩展实际上很 Trivial 啊。。。

对于增加一个颜色 $x$：$\mathrm{\Delta }=(cnt(x)+1{)}^2-(cnt(x)+1)-(cnt(x{)}^2-cnt(x))=2cnt(x)$。

对于减少一个颜色 $x$：$\mathrm{\Delta }=(cnt(x)-1{)}^2-(cnt(x)-1)-(cnt(x{)}^2-cnt(x))=-2cnt(x)+2$。

细节上注意移动时的两个端点到底那个需要操作，哪个不需要操作。都是些细节问题。

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x) {write(x);putchar(10);}

const ll N=5e4,M=1e3;

inline ll gcd(ll a,ll b) {return (b==0)?a:gcd(b,a%b);}

ll n,m,nn,cnt,sum;
ll a[N+5],pos[N+5],col[N+5];

struct Block{ll l,r;}blo[M+5];

struct Qry{
  ll l,r,ansmole,ansdeno,id;
}q[N+5];

inline bool Cmp1(Qry x,Qry y) {return x.l<y.l;}
inline bool Cmp2(Qry x,Qry y) {return x.r<y.r;}
inline bool Cmp3(Qry x,Qry y) {return x.r>y.r;}
inline bool Cmp4(Qry x,Qry y) {return x.id<y.id;}

inline void Modify(ll from,ll to,bool op) {
  if(from==to) return;
  ll type=((from<to)^op);
  if(type) {
    if(from<to) {
      for(ll i=from+1;i<=to;i++) {sum=sum+2*col[a[i]];col[a[i]]++;}
    }
    else {
      for(ll i=from-1;i>=to;i--) {sum=sum+2*col[a[i]];col[a[i]]++;}
    }
  }
  else {
    if(from<to) {
      for(ll i=from;i<to;i++) {sum=sum-2*col[a[i]]+2;col[a[i]]--;}
    }
    else {
      for(ll i=from;i>to;i--) {sum=sum-2*col[a[i]]+2;col[a[i]]--;}
    }
  }
}

inline void Println(ll mole,ll deno) {
  // printf("mole=%lld deno=%lld\n",mole,deno);
  if(mole==0||deno==0) {printf("0/1\n");return;}
  ll k=gcd(mole,deno);
  mole/=k;deno/=k;
  write(mole);putchar('/');writeln(deno);
}

int main() {

  n=read();m=read();
  nn=max(1ll,(ll)n/(ll)sqrt(m));
  // printf("nn=%lld\n",nn);
  for(ll i=1;i<=n;i++) {a[i]=read();}
  cnt=1;
  for(ll i=1;i<=n;i+=nn,cnt++) {
    blo[cnt].l=i;blo[cnt].r=i+nn-1;if(blo[cnt].r>n) blo[cnt].r=n;
    for(ll j=blo[cnt].l;j<=blo[cnt].r;j++) {pos[j]=cnt;}
    // printf("blo[%lld].l=%lld blo[%lld].r=%lld\n"
    // ,cnt,blo[cnt].l,cnt,blo[cnt].r);
  }
  cnt--;
  for(ll i=1;i<=m;i++) {q[i].l=read();q[i].r=read();q[i].id=i;}

  sort(q+1,q+m+1,Cmp1);
  ll lst=1;
  // printf("cnt=%lld\n",cnt);
  for(ll i=1,j=1;j<=cnt;j++) {
    // printf("j=%lld\n",j);
    while(pos[q[i].l]==j) {
      // printf("q[%lld].l=%lld\n",i,q[i].l);
      // printf("pos[%lld]=%lld\n",q[i].l,pos[q[i].l]);
      i++;
    }
    if(j&1) {sort(q+lst,q+i,Cmp2);}
    else {sort(q+lst,q+i,Cmp3);}
    lst=i;
    // printf("i=%lld j=%lld\n",i,j);
  }
  // printf("lst=%lld\n",lst);

  ll lit=1,rit=1;col[a[1]]++;
  for(ll i=1;i<=m;i++) {
    Modify(rit,q[i].r,0);rit=q[i].r;
    Modify(lit,q[i].l,1);lit=q[i].l;
    ll len=q[i].r-q[i].l+1;
    q[i].ansmole=sum;q[i].ansdeno=len*(len-1);
  }

  sort(q+1,q+m+1,Cmp4);

  for(ll i=1;i<=m;i++) {Println(q[i].ansmole,q[i].ansdeno);}

  return 0;
}