(luogu2709) 小 B 的询问

发表于 分类于 ，

一道莫队算法练手题 ## 题目描述:

给出一个包含 n (n<=50000) 个 1~k (k<=50000) 之间的数的序列， 有 m (m<=50000) 个询问，每次询问给出一个 [l,r] 的区间，求区间中 c (i)^2 的和， 其中 c (i) 表示数字 i 在区间 [l,r] 的重复次数

思路:

离线莫队算法

根据公式 (c+1)2=c2+2*c+1 可以在 O (1) 时间内推出 [l-1,r] 或 [l,r+1]

代码:

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int Mn(50005);
const int Mk(50005);
const int Mm(50005);
int blo[Mn],a[Mn]; //blo:分块号
struct q
{
    int l,r,id; //区间左端, 右端, 询问时间
    bool operator <(const q& x)
    {
        return blo[l]==blo[x.l] ? r<x.r : l<x.l;
    }
}que[Mm];
int k[Mk];
int ans[Mm];
int main()
{
    int n,m;
    scanf("%d %d %*d",&n,&m);
    int unit(sqrt(n)); //单位分块大小
    for(int i(1);i<=n;++i)
        scanf("%d",a+i), blo[i] = i/unit+1;
    for(int i(1);i<=m;++i)
    {
        scanf("%d %d",&que[i].l,&que[i].r);
        que[i].id = i;
    }
    sort(que+1,que+m+1);
    int l(1),r(0),t(0);
    for(int i(1);i<=m;++i)
    {
        while(que[i].l<l) //区间转移
        {
            t += 2*k[a[--l]]+1;
            ++k[a[l]];
        }
        while(que[i].r>r)
        {
            t += 2*k[a[++r]]+1;
            ++k[a[r]];
        }
        while(que[i].l>l)
        {
            t -= 2*k[a[l]]-1;
            --k[a[l++]];
        }
        while(que[i].r<r)
        {
            t -= 2*k[a[r]]-1;
            --k[a[r--]];
        }
        ans[que[i].id] = t; //保存答案
    }
    for(int i(1);i<=m;++i)
        cout << ans[i] << endl;
    return 0;
}