bzoj 2038 小Z的袜子 莫队算法

　　题意

　　　　给你一个长度序列，有多组询问，每次询问(l,r)任选两个数相同的概率。n <= 50000，数小于等于n。

　　莫队算法裸题。

　　莫队算法：将序列分为根号n段，将询问排序，以L所在的块为第一关键字，R为第二关键字排序，以次处理询问O(n^1.5)

　　由于是按L所在的块为第一关键字、R为第二关键字排序的，所以在每块内L的变化最多为n，总O(n^1.5)；R在每块内递增，每块内变化最多为n，总O(n^1.5)，故O(n^1.5)。

　　具体可以抽象为二维的点来理解。

　　概率p = sigma(c[i]*(c[i]-1))/(r-l+1) = (sigma(c[i]*c[i])-(r-l+1))/(r-l+1)，c[i]为区间中数i的个数，只需要维护sigma(c[i]*c[i])即可。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <string>

#include <algorithm>

#include <iostream>

#include <cmath>

using namespace std;

typedef long long LL;

const int maxn = ;

int n, m, a[maxn], pos[maxn];

LL s[maxn], ansA[maxn], ansB[maxn], sum;

struct Query{

  int l, r, id;

  Query(int l = , int r = , int id = ):

      l(l), r(r), id(id) {}

  bool operator < (const Query &AI) const{

    if (pos[l] == pos[AI.l])

      return r < AI.r;

    return pos[l] < pos[AI.l];

  }

}b[maxn];

void update(int p, LL d){

  sum -= s[p]*s[p];

  s[p] += d;

  sum += s[p]*s[p];

}

LL gcd(LL x, LL y){

  if (y == )

    return x;

  return gcd(y, x%y);

}

void work(){

  for (int i = , l = , r = ; i <= m; ++i){

    for (; l < b[i].l; ++l)

      update(a[l], -1LL);

    for (; l > b[i].l; --l)

      update(a[l-], 1LL);

    for (; r < b[i].r; ++r)

      update(a[r+], 1LL);

    for (; r > b[i].r; --r)

      update(a[r], -1LL);

    if (l == r){

      ansA[b[i].id] = , ansB[b[i].id] = ;

      continue ;

    }

    ansA[b[i].id] = sum-(r-l+);

    ansB[b[i].id] = LL(r-l+)*LL(r-l);

    LL k = gcd(ansA[b[i].id], ansB[b[i].id]);

    ansA[b[i].id] /= k, ansB[b[i].id] /= k;

  }

}

int main(){

  scanf("%d %d", &n, &m);

  for (int i = ; i <= n; ++i)

    scanf("%d", &a[i]);

  for (int i = ; i <= m; ++i)

    scanf("%d %d", &b[i].l, &b[i].r), b[i].id = i;

  int block = int(sqrt(n));

  for (int i = ; i <= n; ++i)

    pos[i] = (i-)/block+;

  sort(b+, b+m+);

  work();

  for (int i = ; i <= m; ++i)

    printf("%lld/%lld\n", ansA[i], ansB[i]);

  return ;

}