CSES - Shared codeLink to this code:
https://cses.fi/paste/4c432ea7de710eac40593c/
/* God is Great !
Author : SANIDHIYA*/
#include<bits/stdc++.h>
using namespace std;
set<int> combine(set<int> a, set<int> b){
set<int> c;
for(auto elem : a) c.insert(elem);
for(auto elem : b) c.insert(elem);
return c;
}
set<int> identity(){
set<int> temp;
return temp;
}
template<class T,T(*combine) (T,T),T(*identity)()>
class SegmentTree{
private :
int n;
T *t;
void build(vector<T> &a, int v, int tl, int tr) {
if (tl == tr) {
t[v] = a[tl];
} else {
int tm = (tl + tr) / 2;
build(a, v*2, tl, tm);
build(a, v*2+1, tm+1, tr);
t[v] = combine(t[v*2],t[v*2+1]);
}
}
T run_query(int v, int tl, int tr, int l, int r) {
if (l > r)
return identity();
if (l == tl && r == tr) {
return t[v];
}
int tm = (tl + tr) / 2;
return combine(run_query(v*2, tl, tm, l, min(r, tm))
,run_query(v*2+1, tm+1, tr, max(l, tm+1), r));
}
void run_update(int v, int tl, int tr, int pos, int new_val) {
if (tl == tr) {
t[v] = new_val;
} else {
int tm = (tl + tr) / 2;
if (pos <= tm)
run_update(v*2, tl, tm, pos, new_val);
else
run_update(v*2+1, tm+1, tr, pos, new_val);
t[v] = combine(t[v*2],t[v*2+1]);
}
}
public:
SegmentTree(vector<T> &a){
this->n = a.size();
this->t = new T[4*(n + 1)];
build(a, 1, 0, n-1);
}
T query(int l, int r){
return run_query(1, 0, n-1, l, r);
}
void update(int pos, T new_val){
run_update(1, 0, n-1, pos, new_val);
}
};
void solve()
{
vector<set<int>> temp(int(2e5 + 5));
int n, q;
cin >> n >> q;
for(int i = 1; i <= n ; i++ ){
int t;
cin >> t;
temp[i].insert(t);
}
SegmentTree<set<int>, combine, identity> sg(temp);
while(q--){
int l, r;
cin >> l >> r;
cout<<sg.query(l,r).size()<<"\n";
}
}
int main()
{
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
solve();
return 0;
}