黑暗爆炸 2038. 小Z的袜子

发表于 分类于

链接

https://darkbzoj.tk/problem/2038

题意

$n$ 只袜子，问区间内抽到两只相同颜色袜子的概率，共有 $m$ 次询问

思路

普通莫队

对询问分块，这是一种离线做法

先将左端点分成 $\sqrt{n}$ 块，按块从小到大排序，再在相同块内按右端点从小到大排序

在相同块内左端点每次移动小于 $\sqrt{n}$ 步，右端点为单调移动

以上一次询问答案为基础，左端点移动需 $O(\sqrt{n})$，在相同块内右端点总移动需 $O(n)$，因此时间复杂度为 $O(n \sqrt{n})$

对于答案的更新：分母为所有袜子中抽取两只袜子的组合数，分子为同一颜色的袜子中抽取两只袜子的组合数的累加和，端点每次移动一步，只会对一种颜色的贡献造成改变，因此我们可以将原来分子减去原来该颜色的贡献再加上现在该颜色的贡献即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e4+5;
int n,m,c[N],pos[N];
ll sum[N];
struct node {
    int l,r;
    ll a,b;
    int id;
}ask[N];
bool cmp1(node a,node b) {
    return pos[a.l]==pos[b.l]?a.r<b.r:a.l<b.l;
}
bool cmp2(node a,node b) {
    return a.id<b.id;
}
ll gcd(ll a,ll b) {
    return b?gcd(b,a%b):a;
}
void solve() {
    int l=1,r=0;
    ll a=0,b=0;
    for(int i=1;i<=m;i++) {
        b=(ll)(ask[i].r-ask[i].l+1)*(ask[i].r-ask[i].l)/2;
        while(l>ask[i].l) l--,sum[c[l]]++,a+=sum[c[l]]*(sum[c[l]]-1)/2-(sum[c[l]]-1)*(sum[c[l]]-2)/2;
        while(l<ask[i].l) sum[c[l]]--,a+=sum[c[l]]*(sum[c[l]]-1)/2-(sum[c[l]]+1)*sum[c[l]]/2,l++;
        while(r>ask[i].r) sum[c[r]]--,a+=sum[c[r]]*(sum[c[r]]-1)/2-(sum[c[r]]+1)*sum[c[r]]/2,r--;
        while(r<ask[i].r) r++,sum[c[r]]++,a+=sum[c[r]]*(sum[c[r]]-1)/2-(sum[c[r]]-1)*(sum[c[r]]-2)/2;
        if(ask[i].l==ask[i].r) {ask[i].a=0,ask[i].b=1;continue;}
        ll GCD=gcd(a,b);
        ask[i].a=a/GCD,ask[i].b=b/GCD;
    }
    sort(ask+1,ask+1+m,cmp2);
    for(int i=1;i<=m;i++) cout<<ask[i].a<<"/"<<ask[i].b<<endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    int t=sqrt(n);
    for(int i=1;i<=n;i++) cin>>c[i],pos[i]=i/t+1;
    for(int i=1;i<=m;i++) cin>>ask[i].l>>ask[i].r,ask[i].id=i;
    sort(ask+1,ask+1+m,cmp1);
    solve();
    return 0;
}