莫队算法 [国家集训队]小Z的袜子

时间：2021-05-04 06:52:09

题目链接   洛古   https://www.luogu.org/problemnew/show/P1494

大概说下自己的理解

先来概率的计算公式   ∑C(2,f(i))  /  C(2,r−l+1)   f(i)是区间每种颜色袜子的数目

最后推出来的式子是 ∑f(i)*f(i)-(r−l+1)/ C(2,r−l+1)  (我也不知道怎么推的.......别人给的);

单纯的暴力就不说了  o(n*n*n);

说下和  o(n*n) 的;

莫队是 o(n*sqrt(n));

o(n*n)的算法 有两种   一是[l，r] 区间里用个小技巧   从头扫到尾   一开始ans=10；

看到第一个 1  我们+0； 看到第二个 1  我们+1； -0；第三1； +3；-1；

每次都   ans1=ans1-sum[a[j]]*(sum[a[j]]-1);   sum[a[j]]++;   ans1=ans1+sum[a[j]]*(sum[a[j]]-1);   莫队也有这个技巧

第二种是区间转移  从[a，b] 到[p, q]  a-〉p  b-q;  按照预先的排序  稍微 比o(n*n) 小一点；

莫队算法

每次区间转移都可能转移  n个数

莫队把（1-n） 分成sqrt块  每块转移       在每块里   最多 sqrt（n）+n  所以最后  sqrt（n）*（n+sqrt（n））；

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int maxn=5e4+;

int n,m,unit,ans;

int col[maxn],be[maxn],sum[maxn];

struct Mo  { int l,r,ID,A,B; }q[maxn];

int S(int x) {return x*x; }

bool cmp(Mo a,Mo b){return be[a.l]==be[b.l]?a.r<b.r:a.l<b.l;}

bool CMP(Mo a,Mo b){return a.ID<b.ID;}

void revise(int x,int add)

{

    ans-=S(sum[col[x]]);

    sum[col[x]]+=add;

    ans+=S(sum[col[x]]);

}

int32_t main()

{

    cin>>n>>m;  unit=sqrt(n);

    for(int i=;i<=n;i++) cin>>col[i],be[i]=i/unit+;

    for(int i=;i<=m;i++) cin>>q[i].l>>q[i].r,q[i].ID=i;

    sort(q+,q+m+,cmp);

    int l=;

    int r=;

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

    {

       // cout<<q[i].l<<"  "<<q[i].r<<endl;

        while(l<q[i].l)revise(l,-),l++;

        while(l>q[i].l)revise(l-,),l--;

        while(r<q[i].r)revise(r+,),r++;

        while(r>q[i].r)revise(r,-),r--;

        if(q[i].l==q[i].r){q[i].A=;q[i].B=;continue;}

        q[i].A=ans-(q[i].r-q[i].l+);

        q[i].B=(q[i].r-q[i].l+)*(q[i].r-q[i].l);

        int c=__gcd(q[i].A,q[i].B); q[i].A=q[i].A/c; q[i].B=q[i].B/c;

    }

    sort(q+,q+m+,CMP);

    for(int i=;i<=m;i++) printf("%lld/%lld\n",q[i].A,q[i].B);

    return ;

}

相关文章