# Range Distinct values queries

Judge Time:分塊(550ms)>持久化線段樹(310ms)>BIT(270ms)

## 分塊-莫隊算法
詳見[分塊演算法](/86kWJsh6S5KjPzYLc1xsxg)
:::spoiler code

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define mem(a) memset(a,0,sizeof(a))
#define binary_search
#define inf LLONG_MAX
#define mod 1000000007
#define MAXN 1000005
int N=1,n,m,x,k;
//-----------------------------------
int a[MAXN];
struct Q{
	int F,S,i;
};
 
bool cmp(Q a,Q b){
    if(a.F/k==b.F/k){
          if((a.F/k)%2) return a.S>b.S;
          else return a.S<b.S;
    }
    return a.F/k<b.F/k;
}
 
int l,r,cnt;
int mp[MAXN];
 
void sub(int x){
	mp[a[x]]--;
	if(!mp[a[x]]) cnt--;
}
 
void add(int x){
	if(!mp[a[x]]) cnt++;
	mp[a[x]]++;
}
 
int query(int lb,int rb){
	while(l<lb) sub(l++);
	while(l>lb) add(--l);
	while(r>rb) sub(r--);
	while(r<rb) add(++r);
	return cnt;
}
 
void solve(){
	int q;
	cin >> n;
	k=sqrt(n)+1;
	
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	
	cin >> q;
	vector<Q> que(q);
	for(int i=0;i<q;i++){
		cin >> que[i].F >> que[i].S;
		que[i].i=i;
	}
	
	sort(all(que),cmp);
	
	vector<int> ans(q);
	for(int i=0;i<q;i++){
		ans[que[i].i]=query(que[i].F,que[i].S);		
	}
	
	for(auto i:ans) cout << i << '\n';
}
 
signed main(){
    cin.sync_with_stdio(0),cin.tie(0);
    //cin >> N;
    for(int Case=1;Case<=N;Case++){
        solve();
    }
}

:::

---------------------
記錄在[1,i]區間出現的同一個數中最右邊的index,然後設一個cnt陣列,把這個index的位置+1,這樣在查詢區間[l,r]的時候就等於在cnt中,把r的prefix_sum-l的prefix_sum就是答案

## BIT
那既然要計算前綴和,BIT是很好的選擇,但只能離線處理
作法:先照右界排序,確保單調性以及線性複雜度,在插入時,如果a_i已被紀錄,則先把原本a_i的position刪除,再新增當前position

=>速度快,離線

:::spoiler code

#include <bits/stdc++.h>	
#define int long long
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define mem(a) memset(a,0,sizeof(a))
#define bs binary_search
inline void print(vector<int> &arr){for(auto &i:arr) cout << i << '\n';}
inline void read(vector<int> &arr){for(auto &i:arr) cin >> i;}
const int MAXN=4e5+5;
const int inf=1e18+5;
const int mod=1e9+7;
int N=1,n,m,k,ans;
//-----------------------------------
int L,R,cnt,a[MAXN],ins[MAXN];

struct node{
	int l,r,idx;
	bool operator<(node b){
		return r<b.r;
	}
};

int bit[MAXN];
void update(int x,int v){
	x++;
	while(x<MAXN){
		bit[x]+=v;
		x+=x&-x;
	}
}

int query(int x){
	x++;
	int ans=0;
	while(x){
		ans+=bit[x];
		x-=x&-x;
	}
	return ans;
}


//check initialization and MAXN
void solve(){
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	int q;
	cin >> q;
	vector<node> Q(q);
	for(int i=0,l,r;i<q;i++){
		cin >> l >> r;
		Q.pb({l,r,i});
	}
	sort(all(Q));
	vector<int> ans(q);
	int now=0;
	for(auto i:Q){
		while(now<=i.r){
			if(ins[a[now]]) update(ins[a[now]],-1);
			update(now,1);
			ins[a[now]]=now;
			now++;
		}
		ans[i.idx]=query(i.r)-query(i.l-1);
	}
	print(ans);
}
	
signed main(){
    cin.sync_with_stdio(0),cin.tie(0);
    //cin >> N;
    for(int Case=1;Case<=N;Case++){
        ans=0;
        solve();
    }
}

:::

## 持久化線段樹
強制在線就要用到持久化線段樹,其概念是相同的,只是做法有些不同
作法:對於每個i都建立一顆[1,i]線段樹,查詢的時候就去找右界相應的線段樹,在該顆線段樹中遞迴查詢

=>速度慢,在線

:::spoiler code

#include <bits/stdc++.h>	
#define int long long
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define mem(a) memset(a,0,sizeof(a))
#define bs binary_search
inline void print(vector<int> &arr){for(auto &i:arr) cout << i << '\n';}
inline void read(vector<int> &arr){for(auto &i:arr) cin >> i;}
const int MAXN=1e6+5;
const int inf=1e18+5;
const int mod=1e9+7;
int N=1,n,m,k,ans;
//-----------------------------------
int lsun[MAXN<<2],rsun[MAXN<<2],sum[MAXN<<2],a[MAXN],root[MAXN],used[MAXN],idx;

int update(int l,int r,int pre,int target,int value){
	int now=++idx;
	lsun[now]=lsun[pre];
	rsun[now]=rsun[pre];	
	sum[now]=sum[pre]+value;
	
	if(l==r) return now;
	
	int mid=(l+r)>>1;
	if(target<=mid){
		lsun[now]=update(l,mid,lsun[now],target,value);
	}else{
		rsun[now]=update(mid+1,r,rsun[now],target,value);
	}
	return now;
}

int query(int node,int l,int r,int target){
	if(l==r) return sum[node];
	
	int mid=(l+r)>>1;
	if(target<=mid) return sum[rsun[node]]+query(lsun[node],l,mid,target);
	else return query(rsun[node],mid+1,r,target);
}

//check initialization and MAXN
void solve(){
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		if(used[a[i]]){
			root[i]=update(1,n,root[i-1],used[a[i]],-1);
			root[i]=update(1,n,root[i],i,1);
		}else{
			root[i]=update(1,n,root[i-1],i,1);
		}
		used[a[i]]=i;		
	}
	
	int q;
	cin >> q;
	while(q--){
		int lb,rb;
		cin >> lb >> rb;
		cout << query(root[rb],1,n,lb) << '\n';
	}
	
}
	
signed main(){
    cin.sync_with_stdio(0),cin.tie(0);
    //cin >> N;
    for(int Case=1;Case<=N;Case++){
        ans=0;
        solve();
    }
}

:::