HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步 完后，他都会随意取出一
段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此他的项链变得越来越长。有一天，他突然提出了一
个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只
好求助睿智的你，来解决这个问题。
任意门：https://www.lydsy.com/JudgeOnline/problem.php?id=1878
M行，每行一个整数，依次表示询问对应的答案。
莫队裸题，转移的时候判断数字是否唯一即可。
AC code：
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int MAXN = 5e4+10; 4 const int MAXU = 1e6+10; 5 const int MAXQ = 2e5+10; 6 int N, M, lim; 7 int sum[MAXU]; 8 int a[MAXN]; 9 int ans[MAXQ]; 10 struct Query 11 { 12 int l, r, id; 13 }Q[MAXQ]; 14 15 bool cmp(Query a, Query b){ 16 int la = a.l/lim, lb = b.l/lim; 17 if(la != lb) return la < lb; 18 return a.r < b.r; 19 } 20 21 int Move(int x, int v) 22 { 23 int res = 0; 24 if(v == 1 && sum[a[x]] == 0) res++; 25 if(v == -1 && sum[a[x]] == 1) res--; 26 sum[a[x]]+=v; 27 return res; 28 } 29 30 int main() 31 { 32 scanf("%d", &N); 33 for(int i = 1; i <= N; i++){ 34 scanf("%d", &a[i]); 35 } 36 lim = sqrt(N); 37 scanf("%d", &M); 38 for(int i = 1; i <= M; i++){ 39 scanf("%d %d", &Q[i].l, &Q[i].r); 40 Q[i].id = i; 41 } 42 43 sort(Q+1, Q+1+M, cmp); 44 45 int cur = 0, L = 1, R = 0; 46 for(int i = 1; i <= M; i++){ 47 while(Q[i].l < L) cur+=Move(--L, 1); 48 while(Q[i].l > L) cur+=Move(L++, -1); 49 while(Q[i].r < R) cur+=Move(R--, -1); 50 while(Q[i].r > R) cur+=Move(++R, 1); 51 ans[Q[i].id] = cur; 52 } 53 54 for(int i = 1; i <= M; i++){ 55 printf("%d\n", ans[i]); 56 } 57 58 return 0; 59 60 }
BZOJ 1878 [SDOI2009]HH的项链 【莫队】
原文：https://www.cnblogs.com/ymzjj/p/10403069.html