BZOJ1878

发表于 | 分类于 |

题目传送门

Description

给你一个长度为$n$($1\leq n\leq 50000$)的序列$a_i$($1\leq 1000000\leq a_i$)，有$m$($1\leq m\leq 200000$)个询问，每次询问一段区间内有多少个不同的数字。

Input

第一行，一个整数$n$。

第二行，$n$个整数，第$i$个数为$a_i$。

第三行，一个整数$m$。

接下来$m$行，每行两个整数$l$和$r$，表示询问的区间。

Output

$m$行，每行一个整数，依次表示询问的答案。

solution

区间查询直接上莫队。

莫队给排完序后就直接暴力做啦，用一个数组保存当前区间每个数的个数……（做法太简单省略了）。

或者这题还可以用主席树做（这想法贼6）。

不难发现，每个数只有在当前询问区间$[l,r]$内第一次出现才会对答案有贡献，在当前询问区间[l,r]内第二次出现显然没用，那我们用一个数组$last$记录一下第$i$个数上一次出现是在哪里。

如，若$a_i={1,2,3,2,4,1,4,2}$，那么$last_i={0,0,0,2,0,1,5,4}$，这样，问题就变成了求在区间$[l,r]$内，有多少个数小于$l$。

用主席树求就好啦。

Code（莫队）

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
#include<cstdio>
#include<cstdlib>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn=200100;
const int maxm=1001000;
int n,color[maxn],m;
struct Ques
{
	int x,y,sqx,num;
}q[maxn];
bool cmp(Ques a,Ques b)
{
	return a.sqx<b.sqx || (a.sqx==b.sqx && a.y<b.y);
}
int point1,point2,sum[maxm],ans[maxn],Ans;
void add(int x)
{
	if(sum[x]==0) Ans++;
	sum[x]++;
}
void del(int x)
{
	if(sum[x]==1) Ans--;
	sum[x]--;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&color[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&q[i].x,&q[i].y);
		q[i].num=i;
		q[i].sqx=q[i].x/sqrt(n);
	}
	
	sort(q+1,q+1+m,cmp);
	point2=1; 
	for(int i=1;i<=m;i++)
	{
		while(point1<q[i].x-1) del(color[++point1]);
		while(point1>=q[i].x) add(color[point1--]);
		while(point2<=q[i].y) add(color[point2++]);
		while(point2>q[i].y+1) del(color[--point2]);
		ans[q[i].num]=Ans;
	}
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);
	return 0;
}

Code（主席树）

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
77
78
79
80
81
82
83
84
85
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=50010;
const int maxnum=1000100;
int n,num[maxn],last[maxn],posi[maxnum],m;
struct TREE
{
	int sum;
	TREE *lsun,*rsun;
}tree[maxn*40],*root[2*maxn];
TREE* build(int l,int r)
{
	TREE *NewNode=new TREE();
	if(l==r)
		return NewNode;
	int mid=(l+r)>>1;
	NewNode->lsun=build(l,mid);
	NewNode->rsun=build(mid+1,r);
	return NewNode;
}
TREE* add(int x,int l,int r,TREE *u)
{
	TREE *NewNode=new TREE();
	if(l==r)
	{
		NewNode->sum=u->sum+1;
		return NewNode;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
	{
		NewNode->lsun=add(x,l,mid,u->lsun);
		NewNode->rsun=u->rsun;
	}
	else
	{
		NewNode->rsun=add(x,mid+1,r,u->rsun);
		NewNode->lsun=u->lsun;
	}
	NewNode->sum=NewNode->lsun->sum+NewNode->rsun->sum;
	return NewNode;
}
int count(TREE *u,int fl,int fr,int l,int r)
{
	if(l>=fl&&r<=fr)
		return u->sum;
	int mid=(l+r)>>1;
	int ans=0;
	if(fl<=mid) ans+=count(u->lsun,fl,fr,l,mid);
	if(fr>mid) ans+=count(u->rsun,fl,fr,mid+1,r);
	return ans;
}
int main()
{
	scanf("%d",&n);
	
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&num[i]);
		last[i]=posi[num[i]];
		posi[num[i]]=i;
	}
	root[0]=build(0,n);
	for(int i=1;i<=n;i++)
		root[i]=add(last[i],0,n,root[i-1]);
	
	scanf("%d",&m);
	
	for(int i=1;i<=m;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",count(root[r],0,l-1,0,n)-count(root[l-1],0,l-1,0,n));
	}
	
	return 0;
}