小 Z 的袜子 题解
MatrixGroup
·
·
题解
题意：有长度为 N 的序列 A，M 次询问在 [L,R] 中随机选两个不在同一位置的数值相等的概率。
解法：以下假设 $N,M$ 同阶。
显然只需要计算区间内有多少**对**相等的值。
考虑根号分治。考虑对出现次数的多少分类讨论。
- $A_i$ 出现了至少 $\sqrt N$ 次。这样的**值** $A_i$ 最多有 $\sqrt N$ 个。对于每个这样的值，维护它的前缀和数组，每次询问对于每个这样的值查询其出现次数 $c$，将 $\dfrac{c(c-1)}{2}$ 累加到答案中即可。复杂度 $O(N\sqrt N)$。
- $A_i$ 出现了不到 $\sqrt N$ 次。这样的相等**对**数 $(A_L,A_R)$ 不超过 $N\sqrt N$。我们将询问按照 $R$ 排序，遍历到 $R$ 时将所有的 $L$ 的权值加 $1$。这样，询问 $[L,R]$ 的权值就是 $[L,R]$ 内所有数权值的和。长度为 $N$ 的数组，$O(N\sqrt N)$ 次单点修改，$O(N)$ 次区间和，可以使用分块维护。复杂度 $O(N\sqrt N)$。
综上，复杂度 $O(N\sqrt N)$。
主要代码：
```cpp
const int N=244;
struct fenwick{
int a[50005];
int s[N];
void add(int id)
{
++a[id];
++s[(id-1)/N];
}
int sum(int id)
{
int v=0;
rep(j,id/N)
{
v+=s[j];
}
rep(j,id%N)
{
v+=a[id-j];
}
return v;
}
};
fenwick tree;
int main()
{
cin>>n>>m;
rep1(i,n)
{
cin>>v[i];pos[v[i]].pb(i);
}
rep1(i,50000)
{
if(pos[i].size()>=N)
{
fl[i]=1;special.pb(i);
}
else fl[i]=0;
}
rep(i,special.size()) sp_sum[0].pb(0);
rep1(i,n)
{
rep(j,special.size())
{
sp_sum[i].pb(sp_sum[i-1][j]+(v[i]==special[j]));
}
}
rep1(i,m)
{
cin>>l[i]>>r[i];ids[r[i]].pb(i);
}
rep1(i,n)
{
if(!fl[v[i]])
{
rep(j,pos[v[i]].size())
{
int x=pos[v[i]][j];
if(x<i)
{
tree.add(x);
}
}
}
ll t=tree.sum(i);
rep(j,ids[i].size())
{
int x=ids[i][j];
int L=l[x];
a[x]=t-tree.sum(L-1);
rep(k,special.size())
{
ll t=sp_sum[i][k]-sp_sum[L-1][k];
a[x]+=t*(t-1)/2;
}
b[x]=(i-L+1ll)*(i-L)/2;
if(b[x]==0) b[x]=1;
else
{
ll d=mygcd(a[x],b[x]);
a[x]/=d;b[x]/=d;
}
}
}
rep1(i,m) cout<<a[i]<<'/'<<b[i]<<endl;
return 0;
}