莫队入门
小z的袜子
题意:n个数记ai,ai<=n
m次询问:l~r区间内任意选两个数 求其相同的概率
稍微化简为 求区间内每个数出现次数的平方和
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int>pii;
typedef pair<LL,LL>pll;
const int maxn=1e5;
const int oo=1e9;
LL a[maxn+5],cnt[maxn+5],pos[maxn+5],n,m,L=1,R=0,Ans=0;
struct node
{
LL l,r,id;
}b[maxn+5];
bool cmp(node a,node b)
{
if(pos[a.l]==pos[b.l]) return a.r<b.r;
return pos[a.l]<pos[b.l];
}
pll ans[maxn+5];
void del(int x)
{
Ans-=cnt[a[x]]*cnt[a[x]];
cnt[a[x]]--;
Ans+=cnt[a[x]]*cnt[a[x]];
}
void add(int x)
{
Ans-=cnt[a[x]]*cnt[a[x]];
cnt[a[x]]++;
Ans+=cnt[a[x]]*cnt[a[x]];
}
int main()
{
scanf("%lld %lld",&n,&m);
LL len=sqrt(n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]),pos[i]=i/len;
for(int i=1;i<=m;i++){
scanf("%lld %lld",&b[i].l,&b[i].r);
b[i].id=i;
}
sort(b+1,b+1+m,cmp);
for(int i=1;i<=m;i++){
while(L<b[i].l){
del(L);
L++;
}
while(L>b[i].l){
L--;
add(L);
}
while(R<b[i].r){
R++;
add(R);
}
while(R>b[i].r){
del(R);
R--;
}
LL x=Ans-(b[i].r-b[i].l+1);
LL y=(b[i].r-b[i].l+1)*(b[i].r-b[i].l);
LL gcd=__gcd(x,y);
ans[b[i].id].first=x/gcd;
ans[b[i].id].second=y/gcd;
}
for(int i=1;i<=m;i++){
printf("%lld/%lld\n",ans[i].first,ans[i].first?ans[i].second:1);
}
}