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
| #include <iostream> #include <map> #include <vector> #include <cmath> #include <algorithm> #include <array>
using namespace std; const int maxn = 1e6 + 5;
int N; int A[maxn]; int cnt[maxn];
namespace MD { int ANS[maxn]; int cur_ans; int len; bool cmp(array<int, 3> a1, array<int, 3> a2) { auto [l, r, id] = a1; auto [l2, r2, id2] = a2;
if (l / len != l2 / len) return l < l2; return r < r2; } void inc(int x) { cur_ans -= cnt[A[x]] / 2; cnt[A[x]]++; cur_ans += cnt[A[x]] / 2; } void dec(int x) { cur_ans -= cnt[A[x]] / 2; cnt[A[x]]--; cur_ans += cnt[A[x]] / 2; }
void solve(vector<array<int, 3>> &qs, int n) { len = sqrt(n); int L = 1, R = 0;
sort(qs.begin(), qs.end(), cmp); for (int i = 0; i < qs.size(); i++) { auto [l, r, id] = qs[i]; while (L > l) inc(--L); while (L < l) dec(L++); while (R < r) inc(++R); while (R > r) dec(R--); ANS[id] = cur_ans; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> N; for (int i = 1; i <= N; i++) cin >> A[i]; int Q; cin >> Q; vector<array<int, 3>> qs; for (int i = 1; i <= Q; i++) { int l, r; cin >> l >> r; qs.push_back({l, r, i}); } MD::solve(qs, N); for (int i = 1; i <= Q; i++) cout << MD::ANS[i] << "\n"; return 0; }
|