fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAXN = 30005;
  6. const int MAXVAL = 1000005;
  7.  
  8. int bit[MAXN];
  9. int a[MAXN];
  10. int last_pos[MAXVAL]; 
  11. int ans[200005];     
  12. int n, q;
  13.  
  14.  
  15. struct Query {
  16.     int l, r, id;
  17.     bool operator<(const Query& other) const {
  18.         return r < other.r;
  19.     }
  20. };
  21.  
  22. void update(int idx, int val) {
  23.     for (; idx <= n; idx += idx & -idx)
  24.         bit[idx] += val;
  25. }
  26.  
  27. int getSum(int idx) {
  28.     int sum = 0;
  29.     for (; idx > 0; idx -= idx & -idx)
  30.         sum += bit[idx];
  31.     return sum;
  32. }
  33.  
  34. int main() {
  35.     ios_base::sync_with_stdio(false);
  36.     cin.tie(NULL);
  37.  
  38.     cin >> n;
  39.     for (int i = 1; i <= n; i++) {
  40.         cin >> a[i];
  41.     }
  42.  
  43.     cin >> q;
  44.     vector<Query> queries(q);
  45.     for (int i = 0; i < q; i++) {
  46.         cin >> queries[i].l >> queries[i].r;
  47.         queries[i].id = i; 
  48.     }
  49.     sort(queries.begin(), queries.end());
  50.     int current_query = 0;
  51.     for (int i = 1; i <= n; i++) {
  52.         int val = a[i];
  53.         if (last_pos[val] != 0) {
  54.             update(last_pos[val], -1);
  55.         }
  56.         update(i, 1);
  57.         last_pos[val] = i;
  58.         while (current_query < q && queries[current_query].r == i) {
  59.             int L = queries[current_query].l;
  60.             int R = queries[current_query].r;
  61.             int query_id = queries[current_query].id;
  62.             ans[query_id] = getSum(R) - getSum(L - 1);
  63.             current_query++;
  64.         }
  65.     }
  66.     for (int i = 0; i < q; i++) {
  67.         cout << ans[i] << "\n";
  68.     }
  69.  
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/L3pxje
language:
C++14 (gcc 8.3)
created:
2 days 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!