记录编号	417788	评测结果	AAAAAAAAAA
题目名称	[SDOI 2009] HH的项链	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.648 s
提交时间	2017-06-27 18:40:21	内存使用	17.03 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

namespace IO{
    inline char getc(void);
    inline int in(void);
    inline void write(int x);
    inline void write_all(void);

    char ops[1 << 18], *opt = ops, *const opt_end = ops + (1 << 18);
    char num[14], *p = num;

    inline char getc(void){
        static char buf[1 << 18], *fs, *ft;
        return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
    }

    inline int in(void){
        register int res = 0;
        register char tmp = getc();
        while(!isdigit(tmp)) tmp = getc();
        while(isdigit(tmp))
            res = (res + (res << 2) << 1) + (tmp ^ 48),
            tmp = getc();
        return res;
    }

    inline void write(int x){
        do{
            *(++p) = (x % 10) | 0x30;
            x /= 10;
        }while(x);

        while(*p){
            *(opt++) = *(p--);
            if(opt == opt_end) write_all();
        }
        *(opt++) = '\n';
        if(opt == opt_end) write_all();
        return ;
    }

    inline void write_all(void){
        fwrite(ops, 1, opt - ops, stdout);
        opt = ops;
        return ;
    }
}
using IO::in;
using IO::write;
using IO::write_all;

const int MAXN = 1e6 + 10;

struct DATA{
    int id;
    int l, r;
    
    DATA(){;}
    DATA(int _id, int _r, int _l){
        id = _id, l = _l, r = _r;
    }

    bool operator < (const DATA &a) const {
        return l < a.l;
    }
};

inline void update(int w, int k);
inline int query(int k);

int N, M, mx;
int last[MAXN], next[MAXN];
int x[MAXN];
int ans[MAXN];
bool f[MAXN];
vector<DATA> data;

int main(){ 
#ifndef LOCAL
    freopen("diff.in", "r", stdin);
    freopen("diff.out", "w", stdout);
#endif

    N = in();
    for(int i = 1, s; i <= N; ++i){
        mx = max(mx, s = in());
        if(!last[s]){ 
            last[s] = i;
            f[i] = true;
            update(i, 1);
        } else {
            next[last[s]] = i;
            last[s] = i;
        }
    }
    M = in();
    for(int i = 0; i < M; ++i){
        data.push_back(DATA(i, in(), in()));
    }
    sort(data.begin(), data.end());

    int l = 1;
    for(int i = 0; i < M; ++i){
        for(int j = l; j < data[i].l; ++j) {
            register int now = j;
            while(now < data[i].l && next[now]) now = next[now];
            if(f[now]) continue;
            f[now] = true;
            update(now, 1);
        }
        ans[data[i].id] = query(data[i].r) - query(data[i].l - 1);
        l = data[i].l;
    }

    for(int i = 0, *k = ans; i < M; ++i){
        write(*(k++));
    }

    write_all();
    return 0;
}

inline const bool cmp1(const DATA &a, const DATA &b){
    return a.l < b.l;
}

inline int lowbit(int x){
    return x & (~x + 1);
}

inline void update(int w, int k){
    for(register int i = w; i <= N; i += lowbit(i)) x[i] += k;
    return ;
}

inline int query(int w){
    register int res = 0;
    for(register int i = w; i; i -= lowbit(i)) res += x[i];
    return res;
}