給一個長度為$N$的序列
$Q$筆詢問，每次給定$L,R$，定義$cnt_x$為$[L, R)$中$x$的出現次數
回答$\sum cnt_x^2\times x$。
$1\le N\le 4\times 10^4, 1\le Q\le 4\times 10^5$
第一次看到這題完全沒想法@@，被捏了才知道。
因為需要的參數為出現次數，所以可以直接砸墨隊。
然後就是很標準的墨隊實作了。
複雜度的部分，原本我是取每塊大小為$\sqrt{N}$，這樣複雜度是$\mathcal{O}(Q\sqrt N)$，這題$Q$比$N$大很多，會吃TLE吃到爽。
每塊大小改取$\frac{Q}{\sqrt N}$，複雜度變為$\mathcal{O}(N\sqrt Q)$，就能好好ac了(不過用vector還是會tle幾筆，得改成一般陣列)。
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
| #include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
struct query {
int l, r, b, id;
friend bool operator<(const query &a, const query &b) {
return a.b == b.b ? ((a.r > b.r) ^ (a.b & 1)) : a.b < b.b;
}
};
const int N = 4e4 + 25, Q = 4e5 + 25;
int arr[N], ans[Q], cnt[N], v[N];
query que[Q];
signed main() { EmiliaMyWife
int n, q;
cin >> n >> q;
int sz = int(n / sqrt(q)) + 1, cur = 0;
auto get = [&] (int x) {
return 1LL * cnt[x] * cnt[x] % MOD * v[x] % MOD;
};
auto add = [&] (int x) {
cur = (cur - get(x) + MOD) % MOD;
cnt[x]++;
cur = (cur + get(x)) % MOD;
};
auto sub = [&] (int x) {
cur = (cur - get(x) + MOD) % MOD;
cnt[x]--;
cur = (cur + get(x)) % MOD;
};
for(int i = 0; i < n; i++)
cin >> arr[i], v[i] = arr[i];
sort(v, v + n);
auto v_end = unique(v, v + n);
for(auto &x : arr)
x = lower_bound(v, v_end, x) - v;
for(int i = 0; i < q; i++) {
cin >> que[i].l >> que[i].r;
que[i].r--;
que[i].b = que[i].l / sz;
que[i].id = i;
}
int l = 0, r = -1;
sort(que, que + q);
for(int i = 0; i < q; i++) {
const auto &x = que[i];
while(r < x.r)
add(arr[++r]);
while(l > x.l)
add(arr[--l]);
while(r > x.r)
sub(arr[r--]);
while(l < x.l)
sub(arr[l++]);
ans[x.id] = cur;
}
for(int i = 0; i < q; i++)
cout << ans[i] << '\n';
}
|