[SDOI2009] HH的项链

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1000000;
const int MAXM = 1000000;
const int MAXAI = 1000000;
int n, m;
int a[MAXN + 5];
// 存每个位置为右端点的询问<询问的左端点,询问的编号>
vector<pair<int, int>> q[MAXN + 5];
int ans[MAXM + 5];
// pos[i]：i这个种类最新出现的位置
int pos[MAXAI + 5];
// 树状数组
int t[MAXN + 5], treeN;
int lowbit(int x)
{
    return x & (-x);
}
// 第x个数加k
void update(int x, int k)
{
    for (int i = x; i <= treeN; i += lowbit(i))
        t[i] += k;
}
// 返回前x个数的和
int query(int x)
{
    int res = 0;
    for (int i = x; i >= 1; i -= lowbit(i))
        res += t[i];
    return res;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pos[a[i]] = -1;
    }
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        int l, r;
        cin >> l >> r;
        ans[i] = 0;
        q[r].push_back(make_pair(l, i));
    }
    treeN = n;
    for (int r = 1; r <= n; r++)
    {
        if (pos[a[r]] != -1)
            update(pos[a[r]], -1);
        pos[a[r]] = r;
        update(r, 1);
        for (int i = 0; i < q[r].size(); i++)
        {
            int l = q[r][i].first;
            int id = q[r][i].second;
            ans[id] = query(r) - query(l - 1);
        }
    }
    for (int i = 1; i <= m; i++)
        cout << ans[i] << "\n";
    return 0;
}