Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⢀⣠⡯⠀⠀⠀⢠⡐⠀⠀⠀⠀⠀
- ⠀⠀⠀⢀⣤⠔⠂⠀⠀⠀⢤⣤⣤⣤⣄⣀⣀⣀⣀⡀⠀⢀⣀⣀⣀⡀⠀⠀⠀⢀⢀⣀⣠⣤⣴⣶⣾⠉⠉⠙⣶⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⣰⣿⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀
- ⠀⠀⠰⣿⣷⣾⣿⣷⣴⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠏⠉⠛⢿⣿⣿⣿⣿⣿⣿⣿⠿⠿⣿⣶⣿⣿⣿⣿⣤⣂⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣠⣤⣤⣤⣴⣦⣾⣿⣿⣿⣶⣦⣴⣶⣶⠀
- ⠀⠀⠀⣿⣿⣿⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣤⣶⣶⣿⣿⣿⣿⣿⣿⣿⣯⣤⣤⣿⡿⠿⠿⠿⠛⠛⠛⠛⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣽⣿⣿⡟⢻⣿⣿⣿⡟⣿⣿⣿⣿⠉⠉⠁⠀
- ⠀⠀⠀⣹⣟⣿⣦⠈⠻⠋⢉⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⣿⣿⣿⣠⣾⣿⣿⣏⣤⣾⣿⣿⣿⡆⠀
- ⠀⠀⢀⣿⣿⣿⣿⣦⠀⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠟⢿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡧⠀
- ⠀⠀⢸⣿⣿⣿⣿⣿⡀⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡈⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢻⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠛⡄⠀
- ⠀⠀⠈⠿⠿⠁⣿⣿⣿⠎⠻⣯⠉⠉⠉⠈⠉⠉⠉⠉⠉⠉⠉⠉⠉⠉⢹⣿⢻⠉⠉⠁⠈⠻⢦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠁⠉⠙⠛⠛⢿⣿⠟⠋⠁⠀⠀⠀⠈⠀
- ⠀⠀⠀⠀⠀⠀⢹⣿⡟⠀⠀⠈⠳⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢿⠞⠀⠀⠀⠀⠀⠀⠙⠳⠤⠤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠁⠀⠀⠀⠀⠀⠸⣿⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⠀
- ⠀⠀⠀⠀⠀⠀⢈⡟⠇⠀⠀⠀⠀⠈⠁⠤⠤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⢹⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
- ⠀⠀⠀⠀⠀⠀⠀⠙⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⠂⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⡘⡀⠀
- ⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
- */
- #include <iostream>
- #include <string>
- #include <sstream>
- #include <cmath>
- #include <memory.h>
- #include <algorithm>
- #include <stack>
- #include <deque>
- #include <iomanip>
- #include <stdio.h>
- #include <queue>
- #include <map>
- #include <set>
- #include <unordered_map>
- #include <unordered_set>
- #include <random>
- #include <ctime>
- #include <cstdlib>
- #include <cassert>
- #include <iterator>
- #include <chrono>
- #include <array>
- #define int long long
- #define intt __int128
- #define pii pair <int, int>
- #define debug(x) cerr << (#x) << " " << (x) << endl
- #define pb push_back
- #define all(vc) vc.begin(), vc.end()
- #define fir first
- #define sec second
- #define endl "\n"
- #define un unsigned
- #define INF 1000000009
- #define double long double
- using namespace std;
- const int N = 300001, R = 1 << 20, MOD = 1e9 + 7, ABC = 26, logn = 19;
- const int BUBEN = 550;
- mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
- struct S {
- int first, second, idx;
- S(int a, int b, int c) : first(a), sec(b), idx(c) { }
- S() {}
- };
- bool cmp(S a, S b) {
- if (a.fir / BUBEN == b.first / BUBEN)
- return a.second < b.second;
- return a.fir < b.fir;
- }
- vector<int> cnt(N);
- vector<int> block(BUBEN);
- void add( int x) {
- cnt[x]++;
- if (cnt[x] == 1)
- block[x / BUBEN]++;
- return;
- }
- void del(int x) {
- cnt[x]--;
- if (cnt[x] == 0)
- block[x / BUBEN]--;
- return;
- }
- signed main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- srand(time(0));
- cout.precision(17);
- int n;
- cin >> n;
- vector<int> vc(n);
- set<int> st;
- for (int i = 0; i < n; i++) {
- cin >> vc[i];
- st.insert(vc[i]);
- }
- map<int, int> mp;
- int k = 0;
- while (st.size()) {
- mp[*st.begin()] = k;
- k++;
- st.erase(st.begin());
- }
- for (int i = 0; i < n; i++)
- vc[i] = mp[vc[i]];
- int q;
- cin >> q;
- vector<S> query(q);
- for (int i = 0; i < q; i++) {
- int l, r;
- cin >> l >> r;
- l--;
- r--;
- query[i] = { l, r, i };
- }
- sort(all(query), cmp);
- int nl = -1, nr = -1;
- vector<int> answer(q);
- for (int i = 0; i < q; i++) {
- while (nr + 1 <= query[i].sec) {
- nr++;
- add(vc[nr]);
- }
- while (nr > query[i].sec) {
- del(vc[nr]);
- nr--;
- }
- while (nl + 1 < query[i].fir) {
- nl++;
- del(vc[nl]);
- }
- while (nl >= query[i].fir) {
- add(vc[nl]);
- nl--;
- }
- int ans = 0;
- for (int i : block)
- ans += i;
- answer[query[i].idx] = ans;
- }
- for (int i : answer)
- cout << i << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement