更好的阅读体验:https://www.cnblogs.com/To-Carpe-Diem/p/19434503

大意

给出一段区间的颜色，区间询问，求某段区间两个点颜色相同的概率(用分数表示)

思路

发现询问和查询隔离，考虑莫队。

然后我们的修改是不是只需要考虑多一个或者少一个点，那么这个很好办啊。

如果记当前答案(分子)是 $\text{ans}$，则在加入点的时候，$\text{ans}$ 先加上原来这个新加入点颜色的贡献，如果是删点的花就先把删掉的这个点的贡献减去，$\text{ans}$ 的贡献就减去减掉后的这个贡献。

然后注意 long long 即可。

代码

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

#define int long long
const int MAXN = 50005;
int B = 0;
struct node{
    int l, r, id;
    bool operator < (const node &t) const{
        if(l / B == t.l / B) return r < t.r;
        return l / B < t.l / B;
    }
} q[MAXN];
int cnt[MAXN], col[MAXN];
int n, m, ans1[MAXN], ans2[MAXN], A, BB;

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

void add(int x){
    A += cnt[x];
    cnt[x] ++;
}

void del(int x){
    cnt[x] --;
    A -= cnt[x];
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    
    B = sqrt(n);
    
    for(int i = 1;i <= n;i ++){
        cin >> col[i];
    }
    
    for(int i = 1;i <= m;i ++){
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    
    sort(q + 1, q + m + 1);
    
    for(int l = 1, r = 0, i = 1;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(col[-- l]);
        while(l < q[i].l) del(col[l ++]);
        while(r < q[i].r) add(col[++ r]);
        while(r > q[i].r) del(col[r --]);
        BB = (r - l + 1) * (r - l) / 2;
        int g = gcd(A, BB);
        ans1[q[i].id] = A / g;
        ans2[q[i].id] = BB / g;
    }
    
    for(int i = 1;i <= m;i ++){
        cout << ans1[i] << '/' << ans2[i] << '\n';
    }
    return 0;
}

$ \begin{aligned}ans &= \frac{\binom{num_l}{2} + \binom{num_{l + 1}}{2} + \dots + \binom{num_r}{2}}{\binom{r - l + 1}{2}} \\ &= \frac{num_l(num_l - 1) + num_{l + 1}(num_{l + 1} - 1) + \dots + num_r(num_r - 1)}{(r - l + 1)(r - l)} \\ &= \frac{(num_l^2 + num_{l + 1}^2 + \dots + num_r^2) - (num_l + num_{l + 1} + \dots + num_r)}{(r - l + 1)(r - l)} \\ &= \frac{(num_l^2 + num_{l + 1}^2 + \dots + num_r^2) - (r - l + 1)}{(r - l + 1)(r - l)} \end{aligned} $

而

$ (n + 1)^2 = n^2 + 1 + 2n \\ (n - 1)^2 = n^2 + 1 - 2n $

所以对于每一个询问 $[l, r]$，我们只需要将当前询问的分子加上 $2n + 1$ 即可 $O(1)$ 地将答案扩展至 $[l, r + 1]$ 或 $[l - 1, r]$，而对于缩小区间的操作，同理。

于是，我们可以用 $\mid l' - l \mid + \mid r' - r \mid$ 次操作转移至下一询问区间。

而利用分块，将所处分块作为第一关键字，将右区间作为第二关键字，可以实现 $O(n \sqrt n)$ 的时间复杂度。