[SDOI2009]区间不同数个数 （离线树状数组）

• 前面区间的前缀和的计算值在所有区间都相同，这样我们在查询前缀和时就不会因为每个区间计算前缀和的值不同（当我们在ask(r)-ask(l-1)时，其实是默认了每次的区间前缀和(1~l-1)相同的）
• 区间修改转化为单调修改时只需要改变n个点的状态（也可以说是每个点只被修改一次）

#include<algorithm>
#include <iostream>
#include  <fstream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
//#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
	(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
	(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0; //EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
inline void outt(ll x) {
	if(x>9) outt(x/10);
	putchar(x%10+'0');
}

const int N = 1e6+10;
const int maxn = 1e6+10;

int nxt[maxn],n;

int c[maxn];
void add(int x,int y){
	for( ; x<=n ; x+=x&-x)c[x] += y;
}
int ask(int x){
	int ans = 0;
	for(; x;x-=x&-x)ans+=c[x];
	return ans;
}

void init(){
	CLR(nxt);
	CLR(c);
}
int ans[maxn];
struct ss{
	int l,r,id;
	bool operator <(const ss &a) const{
		return l<a.l;
	}
}q[maxn];

int vis[maxn];
int a[maxn];
int main(){
	scanf("%d", &n);
	init();
	CLR(vis);
	rep(i,1,n){
		scanf("%d", &a[i]);
		if(!vis[a[i]]){
			vis[a[i]] = 1;
			add(i,1);
		}
		vis[a[i]] = i;
	}
	CLR(vis);
	per(i,1,n){
		if(!vis[a[i]])nxt[i] = n+1;
		else{
			nxt[i] = vis[a[i]];
		}
		vis[a[i]] = i;
	}
	int m;
	scanf("%d", &m);
	rep(i,1,m)
		scanf("%d%d", &q[i].l, &q[i].r),q[i].id=i;
	sort(q+1,q+m+1);
	int l=1;
	rep(i,1,m){
		while(l<q[i].l)add(nxt[l],1),++l;
		ans[q[i].id] = ask(q[i].r)-ask(q[i].l-1);
	}
	rep(i,1,m){
		printf("%d\n", ans[i]);
	}
	return 0;	
}