求区间内共有多少种数字（莫队、树状数组、线段树、主席树）

莫队

P3901 数列找不同

此题数据较弱，不强制在线，$O(n\sqrt{n})$可以过
开桶记录每个数据的个数，
删除：从1->0即少了一个种类；
添加：从0->1即多了一个种类。

#include
using namespace std;
const int N=100010;
int n,m,a[N],cnt[N];
long long ans[N];
long long temp=0;

struct section
{
	int l,r,pos,id;
}sec[N];

bool cmp(section x,section y)
{
	if(x.pos==y.pos) return x.r<y.r;
	else return x.pos<y.pos;
}

void add(int pos)
{
	if((++cnt[a[pos]]) == 1) ++temp;
}

void del(int pos)
{
	if((--cnt[a[pos]]) == 0) --temp;
}
int main()
{
	cin>>n>>m;
	int t=sqrt(n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&sec[i].l,&sec[i].r);
		sec[i].pos=(sec[i].l-1)/t+1;
		sec[i].id=i;
	}
	sort(sec+1,sec+m+1,cmp);
	int pl=1,pr=0;
	for(int i=1;i<=m;i++)
	{
		while(pl>sec[i].l) pl--,add(pl);
		while(pr<sec[i].r) pr++,add(pr);
		while(pl<sec[i].l) del(pl),pl++;
		while(pr>sec[i].r) del(pr),pr--;
		//cout<<"sec[i].l:"<
		if(temp==sec[i].r-sec[i].l+1)
			ans[sec[i].id]=1;
		else ans[sec[i].id]=0;
	}
	for(int i=1;i<=m;i++)
	{
		if(ans[i]==1) cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}
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
57
58
59

那就把数据加强QAQ
P1972 [SDOI2009] HH的项链
估摸着就过不了，还是CV过来改改，吸口氧气：

#include
using namespace std;
const int N=1000010;
int n,m,a[N],cnt[N];
long long ans[N];
long long temp=0;

struct section
{
	int l,r,pos,id;
}sec[N];

bool cmp(section x,section y)
{
	if(x.pos==y.pos) return x.r<y.r;
	else return x.pos<y.pos;
}

void add(int pos)
{
	if((++cnt[a[pos]]) == 1) ++temp;
}

void del(int pos)
{
	if((--cnt[a[pos]]) == 0) --temp;
}
int main()
{
	cin>>n;
	int t=sqrt(n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&sec[i].l,&sec[i].r);
		sec[i].pos=(sec[i].l-1)/t+1;
		sec[i].id=i;
	}
	sort(sec+1,sec+m+1,cmp);
	int pl=1,pr=0;
	for(int i=1;i<=m;i++)
	{
		while(pl>sec[i].l) pl--,add(pl);
		while(pr<sec[i].r) pr++,add(pr);
		while(pl<sec[i].l) del(pl),pl++;
		while(pr>sec[i].r) del(pr),pr--;
		//cout<<"sec[i].l:"<
		ans[sec[i].id]=temp;
	}
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);
	return 0;
}


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
57

然鹅这么惨烈吗。。。

对于若干个询问的区间[l,r]，如果他们的r都相等的话，那么项链中出现的同一个数字，一定是只关心出现在最右边的那一个的，例如：

项链是：1 3 4 5 1

那么，对于r=5的所有的询问来说，第一个位置上的1完全没有意义，因为r已经在第五个1的右边，对于任何查询的[L,5]区间来说，如果第一个1被算了，那么他完全可以用第五个1来替代。
以下三种方法均是建立在此基础上。我们均需要记录每个数据上一次出现的位置。

树状数组

对所有查询的区间按照r来排序，然后再来维护一个树状数组，这个树状数组是用来干什么的呢？看下面的例子：

1 2 1 3

对于第一个1，insert(1,1)；表示第一个位置出现了一个不一样的数字，此时树状数组所表示的每个位置上的数字（不是它本身的值而是它对应的每个位置上的数字）是：1 0 0 0

对于第二个2，insert(2,1)；此时树状数组表示的每个数字是1 1 0 0

对于第三个1，因为之前出现过1了，因此首先把那个1所在的位置删掉insert(1,-1),然后在把它加进来insert(3,1)。此时每个数字是0 1 1 0

如果此时有一个询问(l,r)，那么直接求get®-get(l-1)就是答案。

#include
using namespace std;

const int N=1e6+10;
int a[N],c[N],last[N],n,m,ans[N];

struct section
{
	int l,r;
	int id;
}sec[N];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

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

void add(int pos,int val)
{
	for(int i=pos;i<=n;i+=lowbit(i))
		c[i]+=val;
}

int get(int pos)
{
	int sum=0;
	for(int i=pos;i;i-=lowbit(i))
		sum+=c[i];
	return sum;
}

bool cmp(section x,section y)
{
    return x.r<y.r;
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		a[i]=read();
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		sec[i].l=read(),sec[i].r=read();
		sec[i].id=i;
	}
	sort(sec+1,sec+m+1,cmp);//按右端点从小到大排序 
	int now=1;
	for(int i=1;i<=m;i++)
	{
		for(int j=now;j<=sec[i].r;j++)
		{
			if(last[a[j]])
				add(last[a[j]],-1);
			last[a[j]]=j;
			add(j,1);
		}
		now=sec[i].r+1;
		ans[sec[i].id]=get(sec[i].r)-get(sec[i].l-1);
	}
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);
    return 0;
}
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

线段树

对于如下序列：1 2 3 1 5
前缀种类数：1 2 3 3 4
区间[2,5]内部的前缀种类数：1 2 3 4，除了1所在的位置，其他位置对应减1，也就是说把$last[a[i]]$到i内的前缀种类数减1，于是变成一个区间修改操作，可以用线段树实现，单点查询也可实现。

不想写
1

主席树

每次都是先把$last[a[i]]$的位置先改了（之前没有的话就直接继承上一个节点的了），形成树t，再在t的基础上继续修改。查询的时候我们用右端点控制树的版本，而用左端点控制范围。

#include
using namespace std;

const int N=1e6+10;
int n,a[N],root[N],last[N],ans[N],tot,m;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
struct Node
{
    int l,r;
    int cnt;
}tr[N*40];


int build(int l,int r)
{
    int p=++tot;
    if(l==r) return p;
    int mid=(l+r)>>1;
    tr[p].l=build(l,mid),tr[p].r=build(mid+1,r);
    return p;
}

int insert(int p,int idx,int l,int r,int x)
{
    int q=++tot;//点分裂
    tr[q]=tr[p],tr[q].cnt+=x;
	if(l<r)
	{
		int mid=(l+r)>>1;
	    if(idx<=mid) tr[q].l=insert(tr[p].l,idx,l,mid,x);
	    else tr[q].r=insert(tr[p].r,idx,mid+1,r,x);
	}
	return q;
}

int query(int idx,int q,int l,int r)
{
	if(l==r) return tr[q].cnt;
	int mid=l+r>>1;
	if(idx<=mid) return query(idx,tr[q].l,l,mid)+tr[tr[q].r].cnt;
	else return query(idx,tr[q].r,mid+1,r);
}

int main()
{
	cin>>n;
	root[0]=build(1,n);
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		if(!last[a[i]])//该数据第一次出现 
			root[i]=insert(root[i-1],i,1,n,1);
		else
		{
			int t=insert(root[i-1],last[a[i]],1,n,-1);
			root[i]=insert(t,i,1,n,1);
		}
		last[a[i]]=i;
	}
    cin>>m;
    for(int i=1;i<=m;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",query(l,root[r],1,n));
	}
    return 0;
}


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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76