(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=c^2+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;
}