Advertisement
ke_timofeeva7

различные числа (Мо)

Mar 2nd, 2024
906
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.82 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <sstream>
  4. #include <vector>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <memory.h>
  8. #include <stdio.h>
  9. #include <stack>
  10. #include <deque>
  11. #include <queue>
  12. #include <set>
  13. #include <iterator>
  14. #include <map>
  15. #include <iomanip>
  16. #include <unordered_map>
  17. #include <unordered_set>
  18. #include <array>
  19. //#define int long long
  20. #define pb push_back
  21. #define fir first
  22. #define sec second
  23. #define double long double
  24. #define endl "\n"
  25. #define un unsigned
  26. #define INF 1000000000009
  27. #define EPS 0.000000000001
  28. #define pii pair<int, int>
  29. #define all(v) v.begin(), v.end()
  30. using namespace std;
  31.  
  32. const int N = 1000009, R = 1 << 20, logn = 19, ABC = 26, BUBEN = 350;
  33.  
  34. struct S {
  35.     int first, second, id;
  36.     S(int a, int b, int c) : fir(a), sec(b), id(c) {}
  37.     S() {}
  38. };
  39.  
  40. bool cmp(S a, S b) {
  41.     if (a.first / BUBEN == b.first / BUBEN)
  42.         return a.second < b.second;
  43.     return a.first < b.first;
  44. }
  45.  
  46. signed main() {
  47.     ios_base::sync_with_stdio(false);
  48.     cin.tie(0);
  49.     cout.tie(0);
  50.  
  51.     int n;
  52.     cin >> n;
  53.  
  54.     vector<int> vc(n);
  55.  
  56.     for (int& i : vc)
  57.         cin >> i;
  58.  
  59.     vector<int> a = vc;
  60.     sort(all(a));
  61.     a.erase(unique(all(a)), a.end());
  62.  
  63.     for (int i = 0; i < n; i++)
  64.         vc[i] = lower_bound(all(a), vc[i]) - a.begin();
  65.  
  66.     int q;
  67.     cin >> q;
  68.  
  69.     vector<S> query(q);
  70.     int id = 0;
  71.     for (auto& i : query) {
  72.         cin >> i.first >> i.second;
  73.         i.id = id;
  74.         id++;
  75.     }
  76.     sort(all(query), cmp);
  77.  
  78.     int pr = -1;
  79.     int ll = -1, rr = -1;
  80.     vector<int> cnt(a.size());
  81.     vector<int> ans(q);
  82.     int answer = 0;
  83.     for (int i = 0; i < q; i++) {
  84.         int l = query[i].first, r = query[i].second;
  85.         l--;
  86.         r--;
  87.         if (pr == -1) {            
  88.             for (int j = l; j <= r; j++) {
  89.                 cnt[vc[j]]++;
  90.                 if (cnt[vc[j]] == 1)
  91.                     answer++;
  92.             }
  93.             ll = l;
  94.             rr = r;
  95.             pr = 0;
  96.         }
  97.         else {
  98.             while (ll > l) {
  99.                 ll--;
  100.                 cnt[vc[ll]]++;
  101.                 if (cnt[vc[ll]] == 1)
  102.                     answer++;
  103.             }
  104.             while (rr < r) {
  105.                 rr++;
  106.                 cnt[vc[rr]]++;
  107.                 if (cnt[vc[rr]] == 1)
  108.                     answer++;
  109.             }
  110.  
  111.             while (ll < l) {
  112.                 cnt[vc[ll]]--;
  113.                 if (cnt[vc[ll]] == 0)
  114.                     answer--;
  115.                 ll++;
  116.             }
  117.             while (rr > r) {
  118.                 cnt[vc[rr]]--;
  119.                 if (cnt[vc[rr]] == 0)
  120.                     answer--;
  121.                 rr--;
  122.             }
  123.         }
  124.         ans[query[i].id] = answer;
  125.     }
  126.     for (int i : ans)
  127.         cout << i << endl;
  128.     return 0;
  129. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement