SPOJ 3267

#include <iostream>
#include <sstream>
#include <bitset>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <numeric>
#include <list>
#define FOR(i,A) for(typeof (A).begin() i = (A).begin() ; i != (A).end() ; i++)
#define mp make_pair
#define debug( x ) cout << #x << " = " << x << endl
#define clr(v,x) memset( v, x , sizeof v )
#define all(x) (x).begin() , (x).end()
#define rall(x) (x).rbegin() , (x).rend()
#define ones(x) __builtin_popcount( x )
#define f(i,a,b) for(int i = a ; i < b ; i++)
#define fd(i,a,b) for(int i = a ; i >= b ; i--)
#define PI acos( -1.0 )
#define EPS 1E-9
#define TAM 200010

using namespace std;

typedef pair<int,int> ii ;
typedef long long ll ;
typedef long double ld ;
typedef pair<int,ii> pii ;

int r[ 200010 ] ;
ii in[ TAM ] ;
int num[ 1000010 ] ;
vector<int> g[ 1000010 ] ;
int v[ 30010 ] ;
int bit[ 30010 ] ;
int n , q ;

void update( int x , int val ){
    for( ; x <= n ; x += x & -x ) bit[ x ] += val ;
}

int sum( int x ){
    int R = 0 ;
    for( ; x > 0 ; x -= x & -x ) R += bit[ x ] ;
    return R ;
}

int main(){

    scanf("%d" , &n ) ;
    f( i , 0 , n ) scanf("%d" , &v[ i ] ) ;
    scanf("%d" , &q ) ;
    f( i , 0 , q ){
        scanf("%d%d" , &in[ i ].first , &in[ i ].second ) ;
        g[ in[ i ].second - 1 ].push_back( i ) ;
    }

    clr( num , -1 ) ;
    f( i , 0 , n ){
        if( num[ v[ i ] ] < 0 ){
            update( i+1 , 1 ) ;
            num[ v[ i ] ] = i ;
        }else{
            update( num[ v[ i ] ]+1 , -1 ) ;
            num[ v[ i ] ] = i ;
            update( i+1 , 1 ) ;
        }
        f( j , 0 , g[ i ].size() ){
            ii input = in[ g[ i ][ j ] ] ;
            int val = sum( input.second ) - sum( input.first - 1 ) ;
            r[ g[ i ][ j ] ] = val ;
        }
    }
    f( i , 0 , q ) printf("%d\n" , r[ i ] ) ;

    return 0 ;
}