洛谷 p1494 小Z的袜子

Description

详见链接: https://www.luogu.org/problemnew/show/P1494

莫队算法

学习一个算法，除了理解它的原理之外，要清楚它的特点，以此来思考适合解决何种问题

莫队算法：区间各元素属性和（累积）查询问题

此题更新操作

分母就是n * n - n(表示两两袜子之间的随机组合)，分子是一个累加和 - n，累加的内容是该区间内每种颜色i出现次数sum[i]的平方

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 50010;

int n, m;///n个元素,m个询问;
int num, bel[N];///分块个数，每块标号
int a[N], sum[N];///元素值与其在相应区间上出现次数
ll ans;///当前区间查询所得答案

struct edge
{
    int l, r, id;
    ll fro, bac;
}e[N];

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

bool cmp_id(edge a, edge b)
{
    return a.id < b.id;
}

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

void update(int x, int change)
{
    ans -= sum[ a[x] ] * sum[ a[x] ];///减去原来的答案
    sum[ a[x] ] += change;           ///更新
    ans += sum[ a[x] ] * sum[ a[x] ];///加上更新后的答案
}

int main()
{
    scanf("%d%d", &n, &m);

    ///1.输入元素并分块
    num = sqrt(n);
    for(int i = 1; i <= n; ++i)///下标需从1开始
    {
        scanf("%d", &a[i]);
        bel[i] = i / num + 1;
    }

    ///2.输入查询区间并记下id并排序
    for(int i = 0; i < m; ++i)
    {
        scanf("%d%d", &e[i].l, &e[i].r);
        e[i].id = i;
    }
    sort(e, e + m, cmp);

    ///3.移动指针更新所查询区间
    int l = 1, r = 0;
    for(int i = 0; i < m; ++i)
    {
        while(l < e[i].l)
            update(l, -1), ++l;
        while(l > e[i].l)
            update(l - 1, 1), --l;
        while(r < e[i].r)
            update(r + 1, 1), ++r;
        while(r > e[i].r)
            update(r, -1), --r;
        if(e[i].l == e[i].r)
        {
            e[i].fro = 0;
            e[i].bac = 1;
            continue;
        }
        e[i].fro = ans - (e[i].r - e[i].l + 1);
        e[i].bac = 1LL * (e[i].r - e[i].l + 1) * (e[i].r - e[i].l);
        ll tem = gcd(e[i].fro, e[i].bac);
        e[i].fro /= tem;
        e[i].bac /= tem;
    }

    ///4.排回原序输出答案
    sort(e, e + m, cmp_id);
    for(int i = 0; i < m; ++i)
        cout << e[i].fro << '/' << e[i].bac << '\n';
    return 0;
}
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

更多关于此题：https://www.cnblogs.com/Paul-Guderian/p/6933799.html