Zhiwei Zhang included in Algorithm

2020-10-07 2020-10-07 302 words 2 minutes

Contents

Description

P2709 小B 有一个长为n的整数序列$a$，值域为$[1,k]$。他一共有m个询问，每个询问给定一个区间$[l,r]$ 求：$\sum_{i=1}^k c_i^2$ 其中 $c_i$ 表示数字 $i$ 在$[l,r]$ 中的出现次数。小B请你帮助他回答询问。

Solution

莫队算法板子题 mark

Code

 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


#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define mem(a,b) memset(a,b,sizeof(a))
#define debug cout<<0<<endl
#define ll long long
const int MAXN = 5e4 + 10;
const int MOD = 1e9 + 7;
using namespace std;

struct Q{
    int l, r, k;
} q[MAXN];

int N, M, K;

int pos[MAXN], a[MAXN], cnt[MAXN];
ll ans[MAXN];
ll res;

inline void Add(int n) {
    cnt[a[n]]++;
    res += 2ll*cnt[a[n]] - 1;
}

inline void Sub(int n) {
    cnt[a[n]]--;
    res -= 2ll*cnt[a[n]] + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M >> K;
    int siz = sqrt(N);
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
        pos[i] = i/siz;
    }
    for (int i = 1; i <= M; i++) {
        cin >> q[i].l >> q[i].r;
        q[i].k = i;
    }
    sort(q+1,q+M+1,[](Q x, Q y){
        return pos[x.l] == pos[y.l] ? x.r < y.r : pos[x.l] < pos[y.l];
    });
    int l = 1, r = 0;
    for (int i = 1; i <= M; i++) {
        while (q[i].l < l) Add(--l);
        while (q[i].r > r) Add(++r);
        while (q[i].l > l) Sub(l++);
        while (q[i].r < r) Sub(r--);
        ans[q[i].k] = res;
    }
    for (int i = 1; i <= M; i++) {
        cout << ans[i] << endl;
    }

    return 0;
}