区间不同数的个数

本文最后更新于：2024年3月7日 下午 

题外话：树状数组作为一个非常易写的结构以及常数很小的算法来说，应用广泛。这篇可能会以后加入到树状数组知识总结里。

朴素的想法就是每个区间都扫一遍，稍微优化一下就是对区间排个序，然后用莫队类似的搞一搞。
但是实际上复杂度还是不够优秀，所以还得继续优化。
思考下，实际上一个区间里“有用的数”会把其他相同的数取代，我们之前记录的是每个区间数字的出现次数，但是我们获得答案只需要直到是否出现了就行。也就是说，我们只让“有用的数”来提供贡献（时空复杂度上的），减少“没用的数”花费的时空复杂度。
呢我们可以只记录相同的数的最后一个，令其贡献为1，在我们对区间排序是以右端点为第一优先级排序的情况下，就能保证扫到某一区间的右端点时我们只需要计算前面被记录的数的个数即可。这时，问题就转化成了单点修改，区间求和的问题。
之后使用树状数组即可。
例题
这里计算的是除这个区间外的不同数个数，用到的技巧是将原数列首尾相连，就能变成一个区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
#define N 200500
using namespace std;
int last[N],team[N],c[N],Ans[N];
inline int lowbit(x){return (x&(-x));}
void updata(int x,int v){for(;x<N;x+=lowbit(x))c[x]+=v;}
int Sum(int x)
{
    int ans=0;
    for(;x>0;x-=lowbit(x))ans+=c[x];
    return ans;
}
struct ss
{
    int l,r,ans,index;
}qu[N];
int n,q,sum;
int cmp(ss a,ss b){return a.r<b.r;}
int main()
{
   while(scanf("%d %d",&n,&q)==2)
   {
        memset(last,0,sizeof(last));
        memset(c,0,sizeof(c));
        sum=0;
        for(int i=1;i<=n;i++)
        {
           scanf("%d",&team[i]);
           team[i+n]=team[i];
        }
        for(int i=1;i<=q;i++)scanf("%d %d",&qu[i].r,&qu[i].l),qu[i].index=i,qu[i].r+=n;
        sort(qu+1,qu+1+q,cmp);
        int c1=1;
        for(int i=1;i<=q;i++)
        {
            for(int j=c1;j<=qu[i].r;j++)
            {
                if(last[team[j]]==0)
                {
                    updata(j,1);
                    last[team[j]]=j;
                }
                else
                {
                    updata(j,1);
                    updata(last[team[j]],-1);
                    last[team[j]]=j;
                }
            }
            c1=qu[i].r+1;
            Ans[qu[i].index]=Sum(qu[i].r)-Sum(qu[i].l-1);
        }
    	for(int i=1;i<=q;i++)printf("%d\n",Ans[i]);
    }
    return 0;
}