fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define sz(o) ((int)o.size())
  5. #define all(o) o.begin(), o.end()
  6. #define rep(i, a, b) for(int i = (a); i <= (b); i++)
  7. #define repr(i, a, b) for(int i = (a); i >= (b); i--)
  8.  
  9. typedef long long int ll;
  10. typedef vector<ll> vll;
  11. typedef vector<int> vi;
  12.  
  13. const int maxa = 1e6, maxq = 2e5;
  14. struct Triplet{
  15.     int l, r, idx;
  16. };
  17. Triplet range[maxq + 10];
  18. int freq[maxa + 10];
  19. int ans[maxq + 10], cur = 0, block;
  20. vi a;
  21.  
  22. void fs(int &nn) {
  23.     bool neg = false;
  24.     register int ch;
  25.     nn = 0;
  26.     ch = getchar();
  27.     if (ch == '-') {
  28.         neg = true;
  29.         ch = getchar();
  30.     }
  31.     for (; (ch > 47 && ch < 58); ch = getchar()) nn = nn * 10 + ch - 48;
  32.     if (neg) nn *= -1;
  33. }
  34.  
  35. void add(int idx){
  36.     freq[a[idx]]++;
  37.     if(freq[a[idx]] == 1) cur++;
  38. }
  39.  
  40. void remove(int idx){
  41.     freq[a[idx]]--;
  42.     if(freq[a[idx]] == 0) cur--;
  43. }
  44.  
  45. void solve() {
  46.     int n, q;
  47.     fs(n);
  48.     block = ceil(sqrt(n));
  49.     a.assign(n + 1, 0);
  50.     rep(i, 1, n) fs(a[i]);
  51.     fs(q);
  52.     rep(i, 1, q){
  53.         fs(range[i].l);
  54.         fs(range[i].r);
  55.         range[i].idx = i;
  56.     }
  57.     sort(range + 1, range + q + 1, [](const Triplet &a, const Triplet &b)->bool{
  58.         if(a.l / block != b.l / block) return a.l / block < b.l / block;
  59.         return a.r < b.r;
  60.     });
  61.     int mo_left = 0, mo_right = 0;
  62.     rep(i, 1, q){
  63.         while(mo_left < range[i].l){
  64.             remove(mo_left);
  65.             mo_left++;
  66.         }
  67.         while(mo_left > range[i].l){
  68.             mo_left--;
  69.             add(mo_left);
  70.         }
  71.         while(mo_right < range[i].r){
  72.             mo_right++;
  73.             add(mo_right);
  74.         }
  75.         while(mo_right > range[i].r){
  76.             remove(mo_right);
  77.             mo_right--;
  78.         }
  79.         ans[range[i].idx] = cur;
  80.     }
  81.     rep(i, 1, q) printf("%d\n", ans[i]);
  82. }
  83.  
  84. int main() {
  85.     #ifndef ONLINE_JUDGE
  86.     freopen("in.txt", "r", stdin);
  87.     freopen("out.txt", "w", stdout);
  88.     #endif
  89.     /*ios_base::sync_with_stdio(false);
  90.     cin.tie(NULL);
  91.     cout.tie(NULL);*/
  92.     cout << setprecision(10);
  93.     clock_t b = clock();
  94.     solve();
  95.     clock_t e = clock();
  96.     cerr << (double(e - b) / CLOCKS_PER_SEC) << " sec";
  97.     return 0;
  98. }
Success #stdin #stdout #stderr 0s 4536KB
comments (?)
stdin
copy 
5
1 1 2 1 3
3
1 5
2 4
3 5
stdout
copy 
3
2
3
stderr
copy 
4.3e-05 sec
https://ideone.com/XPhr5c
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!