#C241107A. [SDOI2009] HH的项链

标签（Label）

莫队算法
模板

网址（Website）

P1972 [SDOI2009] HH的项链 - 洛谷（测试点太严格，但是作为模板还是不错）

【NOI模板】莫队算法 - HH的项链「SDOI2009」 - Super （数据水，可以过）

题目（Problem）

题目描述

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。

有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答…… 因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

输入格式

一行一个正整数 $n$，表示项链长度。
第二行 $n$ 个正整数 $a_i$，表示项链中第 $i$ 个贝壳的种类。

第三行一个整数 $m$，表示 HH 询问的个数。
接下来 $m$ 行，每行两个整数 $l,r$，表示询问的区间。

输出格式

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

样例 #1

样例输入 #1

6
1 2 3 4 3 5
3
1 2
3 5
2 6

样例输出 #1

2
2
4

提示

【数据范围】

对于 $20%$ 的数据，$1\le n,m\leq 5000$；
对于 $40%$ 的数据，$1\le n,m\leq 10^5$；
对于 $60%$ 的数据，$1\le n,m\leq 5\times 10^5$；
对于 $100%$ 的数据，$1\le n,m,a_i \leq 10^6$，$1\le l \le r \le n$。

本题可能需要较快的读入方式，最大数据点读入数据约 20MB

题解（Solution）

$\qquad$方法就是按 $\sqrt{n}$ 分块处理每一个询问，并且对于不在一个块的相邻询问按不同方法排序，然后暴力处理就好。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f;
const int N = 1012345;
bool ST;

struct Wolf{int l,r,id;}b[N];
int pos[N];

int n,q,ans,a[N],as[N];

int cnt[N];
inline void add(int x){if(++cnt[x]==1) ans++;}
inline void del(int x){if(--cnt[x]==0) ans--;}

void Solve(){
	n=rd();int B = sqrt(n);
	For(i,1,n) a[i] = rd(), pos[i]=(i-1)/B+1;
	
	q=rd();For(i,1,q) b[i] = {rd(),rd(),i};
	
	sort(b+1,b+q+1,[&](Wolf a,Wolf b){
		if(pos[a.l]^pos[b.l]) return pos[a.l]<pos[b.l];
		if(pos[a.l] & 1) return a.r>b.r;
		return a.r<b.r;});
	
	int l=1,r=0;
	For(i,1,q){
		int L=b[i].l,R=b[i].r;
		while(l<L) del(a[l++]);
		while(r>R) del(a[r--]);
		while(l>L) add(a[--l]);
		while(r<R) add(a[++r]);
		as[b[i].id] = ans;
	}
	
	For(i,1,q) printf("%d\n",as[i]);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = 1;double Tim = clock();
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}