题解 | #薯片

薯片

使用了树状数组。用一个数组维护对应值的已知的最大右边界。对查询先离线处理，将其右边界从小到大排序。遍历每个查询时先更新到对应的右边界，更新碰到之前出现过的值，把之前的标记取消，更新当前位置的新标记。更新完后就可以用树状数组求和来求区间

#include <bits/stdc++.h>
typedef long long ll;
const ll maxn=1e6+5;
using namespace std;

ll a[maxn];
ll pre[maxn];
ll ans[maxn];
ll tree[maxn];
ll n;ll m;

struct Query{
    ll l,r;
    ll id;
    bool operator < (const Query &x) const{
        return r<x.r;
    }
    
}q[maxn];

ll lowbit(ll x)
{
    return x&(-x);
}

void Update(ll x,ll val)
{
    for(;x<=n;x+=lowbit(x))
        tree[x]+=val;
}

ll cal(ll x)
{
    ll sum=0;
    for(;x>0;x-=lowbit(x))
        sum+=tree[x];
    return sum;
}



int main(){
    
    ll i,j;
    
    scanf("%lld",&n);
    
    for(i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    
    scanf("%lld",&m);
    
    for(i=1;i<=m;i++)
    {
        scanf("%lld%lld",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+m+1);
    
    ll p=1;
    
    for(i=1;i<=m;i++)
    {
        for(;p<=q[i].r;p++)
        {
            if(pre[a[p]])
                Update(pre[a[p]],-1);
            Update(p,1);
            pre[a[p]]=p;
        }
        ans[q[i].id]=cal(q[i].r)-cal(q[i].l-1);
    }
    
    for(i=1;i<=m;i++)
        printf("%lld\n",ans[i]);
    
}