P1972 [SDOI2009]HH的项链
题目描述
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
输入输出格式
输入格式：
第一行：一个整数N，表示项链的长度。
第二行：N 个整数，表示依次表示项链中贝壳的编号（编号为0 到1000000 之间的整数）。
第三行：一个整数M，表示HH 询问的个数。
接下来M 行：每行两个整数，L 和R（1 ≤ L ≤ R ≤ N），表示询问的区间。
输出格式：
M 行，每行一个整数，依次表示询问对应的答案。
输入输出样例
6 1 2 3 4 3 5 3 1 2 3 5 2 6
2 2 4
说明
数据范围：
对于100%的数据，N <= 50000，M <= 200000。
莫队第一A。先膜拜一下莫涛dalao%%%，创造了这个算法。
既然是第一次做莫队，那就顺便讲讲吧。
----------------------------------------------^_^---------------------------------------------
据说，莫队能解决一切区间问题（超强），不过当然要配合着其他一些算法。下面是一个区间询问问题：
给定一个大小为N的数组，数组中所有元素的大小<=N。你需要回答Q个询问。每个询问会给出范围L，R。你需要回答在[ L，R ]中至少出现2次的数字的个数。
如：数组为{ 4，2，1，3，2，2，4，1，1，3 } 查询：L=2，R=5。答案=1。在范围[L，R]中：{ 2，1，3，2 }，只有2是出现至少2次的。
对于这个问题，显然我们有一个n^2的暴力可以写
for each query:
answer = 0 count[] = 0
for i in {l..r}:
count[array[i]]++
if count[array[i]] == 2: answer++
显然,在最坏情况下是n^2的。我们对此进行一下改进：
add(position):
count[array[position]]++
if count[array[position]] == 2:
answer++
remove(position):
count[array[position]]--
if count[array[position]] == 1:
answer--
currentL = 0
currentR = 0
answer = 0
count[] = 0
for each query:
// currentL 应当到 L, currentR 应当到 R
while currentL < L: remove(currentL) currentL++
while currentL > L: add(currentL) currentL--
while currentR < R: add(currentR) currentR++
while currentR > R: remove(currentR) currentR--
output answer
这个算法理论上是n^2的,但是实际运行时还是有所改善的。
最初我们总是从L至R循环，但现在我们从上一次查询的位置调整到当前的查询的位置。
如果上一次的查询是L = 3，R = 10，则我们在查询结束时有currentL=3、currentR=10。如果下一个查询是L = 5，R = 7，则我们将currentL 移动到5，currentR 移动到7。
add 函数 意味着我们添加该位置的元素到当前集合内，并且更新相应的回答。
remove 函数 意味着我们从当前集合内移除该位置的元素，并且更新相应的回答。
接下来就是强大的莫队算法登场了。
莫队算法仅仅调整我们处理查询的顺序(所以前面的铺垫尤为重要!)。
我们得到了Q个查询，我们将把查询以一个特定的顺序进行重新排序，然后处理它们。
显然，这是一个离线算法。每个查询都有L和R，我们称其为“起点”和“终点”。让我们将给定的输入数组分为根号n块。每一块的大小为 根号n。每个“起点”落入其中的一块。每个“终点”也落入其中的一块。
如果某查询的“起点”落在第p块中，则该查询属于第p块。该算法将处理第1块中的查询，然后处理第2块中的查询，等等，最后直到第根号n块。
至此，我们已经有一个顺序、查询按照所在的块升序排列，因此可以有很多的查询属于同一块。
从现在开始，忽略所有的块，只关注我们如何询问和回答第1块。我们将对所有块做同样的事。（第1块中的）所有查询的“起点”属于第1块，但“终点”可以在包括第1块在内的任何块中。
现在让我们按照R值升序的顺序重新排列这些查询。我们也在所有的块中做这个操作。（指每个块块内按R升序排列。）
最终的排序是怎样的？
所有的询问首先按照所在块的编号升序排列（所在块的编号是指询问的“起点”属于的块）。如果编号相同，则按R值升序排列。
例如考虑如下的询问，假设我们会有3个大小为3的块（0-2,3-5,6-8）：{0, 3} {1, 7} {2, 8} {7, 8} {4, 8} {4, 4} {1, 2}
让我们先根据所在块的编号重新排列它们{0, 3} {1, 7} {2, 8} {1, 2}（|）{4, 8} {4, 4}（|）{7, 8}
现在我们按照R的值重新排列 {1, 2} {0, 3} {1, 7} {2, 8}（|）{4, 4} {4, 8}（|）{7, 8}
现在我们使用与上一节所述相同的代码来解决这个问题。上述算法是正确，因为我们没有做任何改变，只是重新排列了查询的顺序。
至此,我们完成了莫队算法，它只是一个重新排序。
可怕的是它的时间复杂度分析。原来，如果我们按照上面指定的顺序，我们所写的O(N^2)的代码运行在O(N根号N)时间复杂度上，那这就挺完美了。（证明略）
（参考资料：MO’s Algorithm (Query square root decomposition)，作者anudeep2011，发表日期为2014-12-28）
----------------------------------------------^_^---------------------------------------------
那么回到题目，我们发现，这就是一道模板题罢了。。。=_=
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
],c[],ans;
struct query{
int L,R,index,ans;
}a[];
inline int read(){
; char ch=getchar();
') ch=getchar();
+ch-',ch=getchar();
return x;
}
bool cmp(query u,query v){return u.L/blocks==v.L/blocks?u.R<v.R:u.L<v.L;}
bool cmp_id(query u,query v){return u.index<v.index;}
);}
);}
int main(){
n=read(),blocks=sqrt(n);
; i<=n; i++) c[i]=read();
Q=read();
; i<=Q; i++)
a[i].L=read(),a[i].R=read(),a[i].index=i;
sort(a+,a++Q,cmp);
,curR=;
memset(cnt,,;
; i<=Q; i++){
while (curL<a[i].L) remove(curL++);
while (curR>a[i].R) remove(curR--);
while (curL>a[i].L) add(--curL);
while (curR<a[i].R) add(++curR);
a[i].ans=ans;
}
sort(a+,a++Q,cmp_id);
; i<=Q; i++) printf("%d\n",a[i].ans);
;
}