田所先生的程序

~众所周知，一般而言，随着经济社会的发展...~

（以上省略114514字）...今天，小编就来给大家带来 田所先生的程序 的...

首先看题，并不复杂，给定一串数列，求区间内不同数字的组数。

如果​~抛开事实不谈~​，这道题似乎可以通过在区间内放集合求长度的方式通过。但显然，这道题会TLE。所以我们需要考虑复杂度更低的方式：

树状数组！

首先来说说具体原理。我们用tree[i]来《树状数组地存储》第i个程序前面的程序数（即前缀和为贝壳种数），用vis[j]来存储j号程序最后一次出现的地方。对所有的询问，以右端点从小到大进行排序，并离线处理。

用pow存储上一个左端点所在的位置，排序后，可证明上一个左端点到现在的右端点区间内，一定存在现在的左端点。

我们的核心代码即为：

int pow=1;
for(int i=1;i<=m;i++){
    for(int j=pow;j<=qu[i].r;j++){
        if(vis[bk[j]])up(bk[j],-1);
        up(bk[j],1);
        vis[bk[j]]=j;
    }
    ans[qu[i].id]=out(qu[i].l-1,qu[i].r);
    pow=qu[i].l+1;
}

那么，完整代码即为：

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int LXB=1e6+10;

int n,m,l,p,k,r;
int bk[LXB],ans[LXB],vis[LXB],tree[LXB];

struct qus
{
    int l,r,id;
}qu[LXB];

void up(int t,int x){
    for(int i=t;i<=n;i+=i&-i)tree[i]+=x;
}

int out(int l,int r){
    int ans=0;
    for(int i=l;i>=1;i-=i&-i)ans-=tree[i];
    for(int i=r;i>=1;i-=i&-i)ans+=tree[i];
    return ans;
}

bool cmp(qus l,qus r){return l.r<r.r;}

signed main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>bk[i];
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>qu[i].l>>qu[i].r;
        qu[i].id=i;
    }
   sort(qu+1,qu+1+m,cmp);
   int pow=1;
   for(int i=1;i<=m;i++){
       for(int j=pow;j<=qu[i].r;j++){
           if(vis[bk[j]])up(bk[j],-1);
           up(bk[j],1);
           vis[bk[j]]=j;
       }
       ans[qu[i].id]=out(qu[i].l-1,qu[i].r);
       pow=qu[i].r+1;
   }
   for(int i=1;i<=m;i++){
       printf("%d\n",ans[i]);
   }
   return 0;//为，美，0
}