小Z的袜子

题目

传送门

做法 & 思路

这题其实是求

$$ \sum_i {cnt[i] \choose 2} \over {r-l+1 \choose 2} $$

$cnt[i]$是颜色i在$[l, r]$中的出现次数

我们知道${a \choose 2} = a \times (a-1) = a^2 - a$

于是, 分子就变成了

$$ {\sum_i{cnt[i]^2} -\sum_i{cnt[i]}} \over {2} $$

分母就变成了

$$ {(r-l+1)^2 - (r-l+1)} \over {2} $$

于是, 一次查询的答案就是

$$ {\sum_i{cnt[i]^2} -\sum_i{cnt[i]}} \over {(r-l+1)^2 - (r-l+1)} $$

我们可以使用莫队算法

其中分子中的$\sum_i{cnt[i]}$是不需要维护的, 因为很明显他就等于$r-l+1$

然后我们只需要维护$\sum_i{cnt[i]^2}$

这题就做完了

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 50010;

int belong[N], block;

int color[N];

struct Query
{   int l, r, id;
    Query() { }
    Query(int _1, int _2, int _3) : l(_1), r(_2), id(_3) { }
} a[N];

bool cmp(Query x, Query y) { return belong[x.l] == belong[y.l] ? x.r < y.r : belong[x.l] < belong[y.l]; }

LL sqr(LL x) { return x * x; }

LL cnt[N];
LL sum;

LL Ans1[N], Ans2[N];

void update(int x, int opt)
{   sum -= sqr(cnt[color[x]]);
    cnt[color[x]] += opt;
    sum += sqr(cnt[color[x]]);
}

LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a % b); }

int main()
{   int n, m;
    scanf("%d %d", &n, &m);
    block = (int) sqrt(n + 0.5);
    for (int i = 1; i <= n; i++)
        belong[i] = (i-1) / block + 1;
    for (int i = 1; i <= n; i++)
        scanf("%d", &color[i]);
    for (int i = 1; i <= m; i++)
        scanf("%d %d", &a[i].l, &a[i].r),
        a[i].id = i;
    sort(a+1, a+1+m, cmp);
    int l = 1, r = 0;
    for (int i = 1; i <= m; i++)
    {   for (; r < a[i].r; r++)
            update(r+1, 1);
        for (; r > a[i].r; r--)
            update(r, -1);
        for (; l < a[i].l; l++)
            update(l, -1);
        for (; l > a[i].l; l--)
            update(l-1, 1);
        if (a[i].l == a[i].r)
        {   Ans1[a[i].id] = 0;
            Ans2[a[i].id] = 1;
            continue;
        }
        Ans1[a[i].id] = sum - (a[i].r - a[i].l + 1);
        Ans2[a[i].id] = sqr((LL) (a[i].r - a[i].l + 1)) - (LL) (a[i].r - a[i].l + 1);
        LL d = gcd(Ans1[a[i].id], Ans2[a[i].id]);
        Ans1[a[i].id] /= d;
        Ans2[a[i].id] /= d;
    }
    for (int i = 1; i <= m; i++)
        printf("%lld/%lld\n", Ans1[i], Ans2[i]);
    return 0;
}

发表于 2018-07-08 10:14:21 in 莫队