BZOJ1878 [SDOI2009]HH的项链(莫队算法)

本文主要是介绍BZOJ1878 [SDOI2009]HH的项链(莫队算法)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一
段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此他的项链变得越来越长。有一天，他突然提出了一
个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

Input

第一行：一个整数N，表示项链的长度。

第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。

第三行：一个整数M，表示HH询问的个数。

接下来M行：每行两个整数，L和R（1 ≤ L ≤ R ≤ N），表示询问的区间。

N ≤ 50000，M ≤ 200000。

Output

M行，每行一个整数，依次表示询问对应的答案。

Sample Input

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

Sample Output

2
2
4

思路

莫队算法的模板题，洛谷上面的数据太强，主席树过了，莫队被卡掉了，BZOJ上面可以用莫队过。

莫队的思想就是加速了暴力的过程，分成了 $\sqrt N$ 个块。排序的时候如果在同一个块里面就按照r从小到大排序，不在同一个块里面就按照l从小到大排序

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],cnt[N];
int tim,ans[N];
int curl=1,curr=0,res=0;
inline int read()
{char ch=getchar();int x=0;while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x;
}
inline void add(int pos)
{cnt[a[pos]]++;if(cnt[a[pos]]==1)res++;
}
inline void remove(int pos)
{cnt[a[pos]]--;if(cnt[a[pos]]==0)res--;
}
struct query
{int l,r,id;
} e[N];
bool cmp(query x,query y)
{if(x.l/tim==y.l/tim)//在同一个块return x.r<y.r;elsereturn x.l<y.l;
}
int main()
{int n,m;n=read();for(int i=1; i<=n; i++)a[i]=read();m=read();tim=sqrt(m);for(int i=1; i<=m; i++){e[i].l=read();e[i].r=read();e[i].id=i;}sort(e+1,e+1+m,cmp);for(int i=1; i<=m; i++){int l=e[i].l,r=e[i].r;while(curl<l) remove(curl++);while(curl>l) add(--curl);while(curr<r) add(++curr);while(curr>r) remove(curr--);ans[e[i].id]=res;}for(int i=1; i<=m; i++)printf("%d\n",ans[i]);return 0;
}
/*
10
1 2 3 1 1 2 1 2 3 1
1
1 2
*/