Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- // tiom4eg's precompiler options
- // POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
- // IO settings
- #define fastIO ios_base::sync_with_stdio(false); cin.tie(0)
- // Quick types
- #define ll long long
- #define ld double
- #define ull unsigned long long
- #define pii pair <int, int>
- #define pll pair <ll, ll>
- #define vi vector <int>
- #define mi vector <vector <int> >
- // Quick functions
- #define endl "\n"
- #define F first
- #define S second
- #define all(a) a.begin(), a.end()
- #define sz(a) a.size()
- #define pb push_back
- #define mp make_pair
- #define fint(n) int n; cin >> n
- #define fstr(s) string s; cin >> s
- #define farr(a, n) int a[n]; for (int pog = 0; pog < n; ++pog) cin >> a[pog]
- // Quick fors
- #define FOR(i, a, b) for (int i = a; i < b; ++i)
- #define RFOR(i, a, b) for (int i = a; i >= b; --i)
- // Pragmas
- #pragma GCC optimize("O3,unroll-loops") // let the chaos begin!
- #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt,tune=native")
- #pragma GCC comment(linker, "/stack:200000000")
- // POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
- using namespace std;
- #include <ext/pb_ds/assoc_container.hpp>
- using namespace __gnu_pbds;
- struct splitmix64 {
- size_t operator()(size_t x) const {
- static const size_t fixed = chrono::steady_clock::now().time_since_epoch().count();
- x += 0x9e3779b97f4a7c15 + fixed;
- x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
- x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
- return x ^ (x >> 31);
- }
- };
- int R = 1;
- struct segtree {
- vi cnt;
- void init() { cnt.resize(2 * R); }
- void inc(int p) {
- p += R;
- while (p) cnt[p]++, p >>= 1;
- }
- void dec(int p) {
- p += R;
- while (p) cnt[p]--, p >>= 1;
- }
- int rsq(int l, int r) {
- int res = 0;
- l += R, r += R;
- while (l < r) {
- if (l & 1) res += cnt[l];
- if (!(r & 1)) res += cnt[r];
- l = (l + 1) >> 1, r = (r - 1) >> 1;
- }
- if (l == r) res += cnt[l];
- return res;
- }
- };
- int main() {
- fastIO;
- int n; cin >> n;
- while (R < n) R <<= 1;
- int a[n]; FOR(i, 0, n) cin >> a[i];
- segtree t;
- t.init();
- gp_hash_table <int, int, splitmix64> pos;
- int q; cin >> q;
- vector <pair <int, pii> > qry(q);
- FOR(i, 0, q) {
- int l, r; cin >> l >> r, l--, r--;
- qry[i] = {i, {l, r}};
- }
- stable_sort(all(qry), [](const auto& p1, const auto& p2){ return p1.S.S < p2.S.S; });
- int ans[q]; FOR(i, 0, q) ans[i] = 0;
- int p = 0;
- FOR(i, 0, n) {
- if (pos.find(a[i]) != pos.end()) t.dec(pos[a[i]]);
- pos[a[i]] = i;
- t.inc(pos[a[i]]);
- while (p < q && qry[p].S.S == i) ans[qry[p].F] = t.rsq(qry[p].S.F, qry[p].S.S), p++;
- }
- FOR(i, 0, q) cout << ans[i] << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement