省选NOI-专题[莫队][分块]：P1494 [国家集训队]小Z的袜子

· · 题解

我这里推荐一下我的博客

在博客里观看更美观哦~

题目

华丽的分割线

解析

此题使用暴力分块的玄学莫队

首先对于区间[l,r],概率分母为(r-l+1)*(r-l)

分子为∑i=l->r num[i]*(num[i]-1) (num[i]>=2)

其中num[i]表示i在区间[l,r]的出现次数

求出分子分母的最大公约数，约分即可。

当分子为0或l==r是特判为0/1

重点讲莫队

一种暴力做法是对于上一问的l,r,将其左右移动到这一问的l,r

在上一问ans及num数组的基础下，将ans减有变动的数i对应的贡献

离开区间的数num[i]--,新加入的数num[i]++，

再让ans加新的数i对应的贡献(num[i]*(num[i]-1))

复杂度为O(nm),会超时

考虑离线做法，将长度为n的序列分成根号n个块，

每个块长度为根号n，将每个区间的l所在块的编号记录下来

以l所在块的编号为第一关键字，r为第二关键字对询问排序

按排序后的顺序重复以上暴力，神奇的事就出现了

右端点在一个块内枚举为O(n),有根号n个块,总复杂度O(n^1.5)

左端点在一个块内为O(根号n),不在一个块内为O(2*根号n)

有m次询问，总复杂度O(m*根号n)

两者的复杂度为O(n^1.5)

代码

#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int N=200000;
void read(int &x)
{
    int f=1;
    x=0;
    char c;
    c=getchar();
    while((c<'0'||c>'9')&&c!='-')
    {
        c=getchar();
    }
    if(c=='-')
    {
        f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    x=x*f;
}
void read(ll &x)
{
    ll f=1;
    x=0;
    char c;
    c=getchar();
    while((c<'0'||c>'9')&&c!='-')
    {
        c=getchar();
    }
    if(c=='-')
    {
        f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    x=x*f;
}
ll a[N];
ll num[N];
struct node
{
    int l;
    int r;
    int id;
    int pos;
    bool operator <(const node now) const;
};
bool node::operator <(const node now) const
{
    return pos==now.pos ? r<now.r : pos<now.pos;
}
node que[N];
struct data
{
    ll up;
    ll dowm;
};
data Ans[N];
inline ll power(ll a)
{
    return a*(a-1);
}
ll gcd(ll a,ll b)
{
    if(b==0)
    {
        return a;
    }
    else
    {
        return gcd(b,a%b);
    }
}
void charge(ll &a,ll &b)
{
    ll g;
    g=gcd(a,b);
    a/=g;
    b/=g;
    return;
}
int main()
{
    int n,m,i,size;
    read(n);
    read(m);
    size=(int)sqrt(n);
    for(i=1;i<=n;i++)
    {
        read(a[i]);
    }
    for(i=1;i<=m;i++)
    {
        read(que[i].l);
        read(que[i].r);
        que[i].id=i;
        que[i].pos=(que[i].l-1)/size+1;
    }
    sort(que+1,que+1+m);
    int l,r;
    ll ans;
    l=1;
    r=0;
    ans=0;
    for(i=1;i<=m;i++)
    {
        while(l>que[i].l)
        {
            l--;
            ans-=power(num[a[l]]);
            num[a[l]]++;
            ans+=power(num[a[l]]);
        }
        while(l<que[i].l)
        {
            ans-=power(num[a[l]]);
            num[a[l]]--;
            ans+=power(num[a[l]]);
            l++;
        }
        while(r<que[i].r)
        {
            r++;
            ans-=power(num[a[r]]);
            num[a[r]]++;
            ans+=power(num[a[r]]);
        }
        while(r>que[i].r)
        {
            ans-=power(num[a[r]]);
            num[a[r]]--;
            ans+=power(num[a[r]]);
            r--;
        }
        if(que[i].l==que[i].r||ans==0)
        {
            Ans[que[i].id].up=0;
            Ans[que[i].id].dowm=1;
        }
        else
        {
            Ans[que[i].id].up=ans;
            Ans[que[i].id].dowm=power(que[i].r-que[i].l+1);
            charge(Ans[que[i].id].up,Ans[que[i].id].dowm);
        }
    }
    for(i=1;i<=m;i++)
    {
        printf("%lld/%lld\n",Ans[i].up,Ans[i].dowm);
    }
}