一.关于莫队
一种离线的关于区间操作的算法。
一般莫队会和以下知识点一起使用：
1.分块思想。
2.离散化。
3.树链剖分/倍增，用于应付树上的（然而本蒟蒻写这篇博客时还不会，后续补充）
二.算法实现
1.SPOJ 3267 D-Query
暴力做法：记录每个数字出现的次数，每个询问统计出现区间内次数不为0的数字个数。
复杂度：O(n2)
显然过不去。
考虑优化方法。每次遇到新数那么它出现次数一定是0，遇到旧数如果后面没有了那么它出现次数一定是1。
用双指针扫区间？
对于每个询问区间用指针移动来代替枚举即可实现上面的优化。
如果区间特别多怎么办？
考虑分块，按照块的下标和每个询问的右端点排序，那么就避免了双指针扫过去又扫回来的情况。
这就是莫队的基本操作了。
总复杂度：O(nlogn）+O（n√n）+O（n√n）=O（n√n）
同时这是一道莫队裸题。本题AC代码：（莫队模板）
1 #include<bits/stdc++.h> 2 using namespace std; 3 struct Query 4 { 5 int l,r,num,pos; 6 bool operator < (const Query &k) const 7 { 8 if(pos==k.pos) return r<k.r; 9 return pos<k.pos; 10 } 11 }q[200020]; 12 int n,m,ans,a[200020],res[200020],cnt[1000020]; 13 int main() 14 { 15 scanf("%d",&n); 16 int size=sqrt(n); 17 for(int i=1;i<=n;i++) 18 { 19 scanf("%d",&a[i]); 20 } 21 scanf("%d",&m); 22 for(int i=1;i<=m;i++) 23 { 24 scanf("%d%d",&q[i].l,&q[i].r); 25 q[i].num=i; 26 q[i].pos=(q[i].l-1)/size+1; 27 } 28 sort(q+1,q+m+1); 29 int l=1,r=0; 30 for(int i=1;i<=m;i++) 31 { 32 while(q[i].l<l) 33 { 34 l--; 35 if(cnt[a[l]]==0) 36 { 37 ans++; 38 } 39 cnt[a[l]]++; 40 } 41 while(q[i].r>r) 42 { 43 r++; 44 if(cnt[a[r]]==0) 45 { 46 ans++; 47 } 48 cnt[a[r]]++; 49 } 50 while(q[i].l>l) 51 { 52 cnt[a[l]]--; 53 if(cnt[a[l]]==0) 54 { 55 ans--; 56 } 57 l++; 58 } 59 while(q[i].r<r) 60 { 61 cnt[a[r]]--; 62 if(cnt[a[r]]==0) 63 { 64 ans--; 65 } 66 r--; 67 } 68 res[q[i].num]=ans; 69 } 70 for(int i=1;i<=m;i++) 71 { 72 printf("%d\n",res[i]); 73 } 74 return 0; 75 }
2.洛谷 P2709 小B的询问
又一道莫队裸题。一个元素进入区间的贡献res=（cnt+1)2-cnt2=2*cnt+1。
1 #include<bits/stdc++.h> 2 using namespace std; 3 struct Query 4 { 5 int l,r,num,pos; 6 bool operator < (const Query &k) const 7 { 8 if(pos==k.pos) return r<k.r; 9 return pos<k.pos; 10 } 11 }q[100001]; 12 int n,m,k,ans,a[100001],cnt[100001],res[100001]; 13 int main() 14 { 15 scanf("%d%d%d",&n,&m,&k); 16 int size=sqrt(n); 17 for(int i=1;i<=n;i++) 18 { 19 scanf("%d",&a[i]); 20 } 21 for(int i=1;i<=m;i++) 22 { 23 scanf("%d%d",&q[i].l,&q[i].r); 24 q[i].num=i; 25 q[i].pos=(q[i].l-1)/size+1; 26 } 27 sort(q+1,q+m+1); 28 int l=1,r=0; 29 for(int i=1;i<=m;i++) 30 { 31 while(q[i].l<l) 32 { 33 l--; 34 cnt[a[l]]++; 35 ans+=2*cnt[a[l]]-1; 36 } 37 while(q[i].r>r) 38 { 39 r++; 40 cnt[a[r]]++; 41 ans+=2*cnt[a[r]]-1; 42 } 43 while(q[i].l>l) 44 { 45 cnt[a[l]]--; 46 ans-=2*cnt[a[l]]+1; 47 l++; 48 } 49 while(q[i].r<r) 50 { 51 cnt[a[r]]--; 52 ans-=2*cnt[a[r]]+1; 53 r--; 54 } 55 res[q[i].num]=ans; 56 } 57 for(int i=1;i<=m;i++) 58 { 59 printf("%d\n",res[i]); 60 } 61 return 0; 62 }
3.洛谷 P1494 小Z的袜子
原文：https://www.cnblogs.com/Rakan-LoveJ/p/11544591.html
