题解【bzoj2038 [2009国家集训队]小Z的袜子(hose)】

Description

\(m\) 个询问，每次给出一个区间，求从这个区间中取出两个数使得它们同色的概率。

\(n,m,a_i \leq 50000\)

Solution

莫队模板题

最后的概率是 选的颜色相同的方案数 / 区间长度 * (区间长度 - 1)，显然，只需要维护方案数。

问题化为知道 \([l,r]\) 的情况下，如何快速算出 \([l \pm 1, r], [l, r \pm 1]\) 的方案数

如果加入一个数 \(x\)，则方案数增加了 $cnt_x * (cnt_x+1) - cnt_x * (cnt_x-1) = 2 * cnt_x $

如果删除一个数 \(x\)，则方案数减少了 \(cnt_x * (cnt_x - 1) - (cnt_x - 1) * (cnt_x - 2) = 2 * (cnt_x-1)\)

其中 \(cnt_x\) 表示 \(x\) 出现的次数。然后就做完了（

注意特判 \(l = r\)（

Code

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 500100;

int n, m, a[N], cnt[N], blo;

ll now, ans1[N], ans2[N];

struct node {

  int l, r, id;

  bool operator < (const node &x) const {

    return l / blo == x.l / blo ? r < x.r : l / blo < x.l / blo;

  }

} Q[N];

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

inline void add(int x) {

  now += 2ll * cnt[a[x]];

  cnt[a[x]]++;

}

inline void del(int x) {

  if(cnt[a[x]] > 0) {

    now -= 2ll * cnt[a[x]] - 2;

    cnt[a[x]]--;

  }

}

int main() {

  scanf("%d %d", &n, &m); blo = sqrt(m);

  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);

  int L = 0, R = 0;

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

    int l = Q[i].l, r = Q[i].r;

    if(l == r) {

      ans1[Q[i].id] = 0, ans2[Q[i].id] = 1;

      continue ;

    }

    while(L > l) add(--L);

    while(R < r) add(++R);

    while(L < l) del(L++);

    while(R > r) del(R--);

    ans1[Q[i].id] = now;

    ans2[Q[i].id] = 1ll * (r - l + 1) * (r - l);

  }

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

    if(!ans1[i]) ans2[i] = 1;

    else {

      int G = gcd(ans1[i], ans2[i]);

      ans1[i] /= G, ans2[i] /= G;

    } printf("%lld/%lld\n", ans1[i], ans2[i]);

  }

  return 0;

}