P1972求大佬调

#include <bits/stdc++.h>
using namespace std;
/*

 */
typedef long long ll;
#define int long long 
typedef pair<int,int>pai;
const int N=1e6+10;
int c[N];
int n;
int a[N];
pai f[N];
pai pref[N];
int back[N];
int lowbit(int x)
{
    return x&(-x);
}
void get(int x,int y)
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        c[i]+=y;
    }
}
int sum(int x)
{
    int ret=0;
    for(int i=x;i>0;i-=lowbit(i))
    {
        ret+=c[i];
    }
    return ret;
}
map<pai,int>mp;
bool cmp(pai a,pai b)
{
    return a.second<b.second;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int q;
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>f[i].first>>f[i].second;
        pref[i]=f[i];
    }
    sort(f+1,f+1+q,cmp);
    int prer=0;
    for(int i=1;i<=q;i++)
    {
        //cout<<cnt[f[i].first]-cnt[f[i].second-1]<<"\n";
        for(int j=prer+1;j<=f[i].second;j++)
        {
            if(back[a[j]]!=0)get(back[a[j]],-1);
            get(j,1);
            back[a[j]]=j;
        }
        mp[f[i]]=sum(f[i].second)-sum(f[i].first-1);
    }
    for(int i=1;i<=q;i++)
    {
        cout<<mp[pref[i]]<<"\n";
    }
    return 0;
}