fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1e5;
  6.  
  7. int                          n, q, a[N + 5], tree[N + 5], qr[N + 5];
  8. vector<tuple<int, int, int>> vqr;
  9. map<int, int>                pos;
  10.  
  11. void update(int i, int x) {
  12.     for (; i && i <= n; i += i & -i) { tree[i] += x; }
  13. }
  14.  
  15. int get(int i) {
  16.     int res = 0;
  17.     for (; i; i -= i & -i) { res += tree[i]; }
  18.     return res;
  19. }
  20.  
  21. int query(int l, int r) {
  22.     return get(r) - get(l - 1);
  23. }
  24.  
  25. int main() {
  26.     cin.tie(0)->sync_with_stdio(0);
  27.     cin >> n >> q;
  28.     for (int i = 1; i <= n; i++) { cin >> a[i]; }
  29.     for (int i = 1; i <= q; i++) {
  30.         int l, r;
  31.         cin >> l >> r;
  32.         vqr.push_back({r, l, i});
  33.     }
  34.     sort(vqr.begin(), vqr.end());
  35.     int k = 1;
  36.     for (auto &[r, l, idx] : vqr) {
  37.         for (; k <= r; k++) {
  38.             update(pos[a[k]], -1);
  39.             update(k, 1);
  40.             pos[a[k]] = k;
  41.         }
  42.         qr[idx] = query(l, r);
  43.     }
  44.     for (int i = 1; i <= q; i++) { cout << qr[i] << "\n"; }
  45. }
  46.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
5 3
1 2 2 3 2
1 3
1 5
3 4
stdout
copy 
2
3
2
https://ideone.com/lubh9G
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!