distinct_values_que.cpp

#include <bits/stdc++.h>
//Author : ritchie_s
#define for0(i, n) for (int i = 0; i < (int)(n); ++i) // 0 based indexing
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i) // 1 based indexing
// Short hand for usual tokens
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define sp " "
// Shorthand for commonly used types
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;
// functions
#define MOD 1000000007
ll min(ll a,int b) { if (a<b) return a; return b; }
ll min(int a,ll b) { if (a<b) return a; return b; }
ll max(ll a,int b) { if (a>b) return a; return b; }
ll max(int a,ll b) { if (a>b) return a; return b; }
ll gcd(ll a,ll b) { if (b==0) return a; return gcd(b, a%b); }
ll lcm(ll a,ll b) { return (a/gcd(a,b))*b; }
string to_upper(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A'; return a; }
string to_lower(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A'; return a; }
bool prime(ll a) { if (a==1) return 0; for (int i=2;i<=round(sqrt(a));++i) if (a%i==0) return 0; return 1; }
// int gcd = __gcd(a,b) , ll LCM = 1LL*a*b/gcd
//fenwick
template <class T>
struct BIT { //1-indexed
  int n; vector<T> t;
  BIT() {}
  BIT(int _n) {
    n = _n; t.assign(n + 1, 0);
  }
  //gives prefix sum from (1 to x )  ||   In frequency counting usage number of elements that are <= x
  T query(int i) {
    T ans = 0;
    for (; i >= 1; i -= (i & -i)) ans += t[i];
    return ans;
  }
  //increase the val at index i by val 
  void upd(int i, T val) {
    if (i <= 0) return;
    for (; i <= n; i += (i & -i)) t[i] += val;
  }
  //increase the val of all numbers btw [l,r] by val 
  void upd(int l, int r, T val) {
    upd(l, val);
    upd(r + 1, -val);
  }
  //gives prefix sum btw [l,r]   ||   in context of frequcency counting -- number of elements(x) l<=x<=r
  T query(int l, int r) {
    return query(r) - query(l - 1);
  }
};
//solver fn
void solve(){
    ll n,q;
    cin>>n>>q;
    vll a(n+1);
    for1(i,n){
        cin>>a[i];
    }

    vvll queries(q , vll(3));
    for(int i = 0 ; i<q ; i++){
        ll l , r;
        cin>>l>>r;
        queries[i][0] = l , queries[i][1] = r , queries[i][2] = i;
    }

    sort(queries.begin() , queries.end() , [](auto &x , auto &y){
        return x[1]<y[1];
    });

    BIT<ll> bit(n);
    map<ll , ll> last;
    vll ans(q);
    ll curr_r = 0;
    for(auto &qr : queries){
        while(curr_r < qr[1]){
            curr_r++;
            ll val = a[curr_r];
            if(last.count(val)){
                bit.upd(last[val] , -1); //remove old occurance
            }
            bit.upd(curr_r , 1); //add new occurance
            last[val] = curr_r;
        }
        ans[qr[2]] = bit.query(qr[0] , qr[1]);
    }

    for(auto x : ans){
        cout<<x<<endl;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;
     int t = 1;
     
     while(t--){
        solve();
     }
    return 0;
}