清橙A1206.小Z的袜子 && CF 86D（莫队两题）
在网上看了一些别人写的关于莫队算法的介绍，我认为，莫队与其说是一种算法，不如说是一种思想，他通过先分块再排序来优化离线查询问题。
应用范围：一般问题是让你回答多个连续区间上的问题，如果你知道了区间【l，r】的答案、你就可以在O（1）或O（logn）时间内知道【l+1，r】、【l，r+1】、【l-1,r】、【l，r-1】区间的答案，那么你就可以应用莫队算法。
实现方法：数组长度为n，查询个数为m。先读入所有查询，然后把查询【l，r】按l/sqrt（m）递增的的顺序排序，如果相同再按r递增的顺序排序，然后维护当前区间的查询值，再按排好的序从前到后暴力跑一遍就OK了。
原理阐述：到这里很多人可能要问一个问题，为什么要分sqrt（m）块？这个问题也困扰了我好久，不过经过一番冥想，我终于找到了答案：假设我们要把查询分成x块，那么每块中 r 的移动量最大为n、总的移动量为n*x，每块中 l 的移动量最大为n/t、总的移动量为m*n/x，整个查询的复杂度为（n*x+n*m/x），根据数学知识我们可以知道，在n*x=n*m/x的时候总的复杂度是最小的，这时x=sqrt（m），复杂度为O（2*n*sqrt（m）），这样莫队按sqrt（m）分块的合理性就得到了证明。
入门题1：青橙A1206.小Z的袜子
长度为n的数组，有m个询问，每个询问你需要回答：在该区间内任意抽两个数字且两个数字的数值相同的概率是多大，答案需要时最简分数的形式。
思路：对于区间【l，r】，其不同数值的数的个数分别为a、b、.....、c，那么上述的概率就是（a^a+b^b+...+c^c-(r-l+1)）/(r-l)*(r-l+1)。（不要问我是咋推出来的）。
解法：维护当前区间【l，r】中数值为v的数的个数cnt【v】，如果该区间答案为temp，那么对于区间【l，r+1】，你可以在O（1）时间内求出新的temp，那么久可以运用莫队来搞定了。
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
using namespace std; const int maxn=;
typedef long long LL;
int n,m; LL gcd(LL a,LL b){
if(b==) return a;
return gcd(b,a%b);
} struct ANS{
LL a,b;
void simple(){
LL kk=gcd(a,b);
a/=kk;
b/=kk;
}
}ans[maxn]; struct node{
int l,r,id;
}q[maxn]; int cmp(const node& a,const node& b){
if(a.l/(int)sqrt(m)!=b.l/(int)sqrt(m)) return a.l/(int)sqrt(m)<b.l/(int)sqrt(m);
return a.r<b.r;
} int c[maxn];
int cnt[maxn]; void solve(){
cnt[c[]]++;
LL temp=;
int l=;
int r=;
for(int i=;i<=m;i++){
//cout<<l<<" "<<r<<endl;
while(l<q[i].l){
temp=temp-cnt[c[l]]*cnt[c[l]];
cnt[c[l]]--;
temp=temp+cnt[c[l]]*cnt[c[l]];
l++;
}
while(l>q[i].l){
l--;
temp=temp-cnt[c[l]]*cnt[c[l]];
cnt[c[l]]++;
temp=temp+cnt[c[l]]*cnt[c[l]];
}
while(r<q[i].r){
r++;
temp=temp-cnt[c[r]]*cnt[c[r]];
cnt[c[r]]++;
temp=temp+cnt[c[r]]*cnt[c[r]];
}
while(r>q[i].r){
temp=temp-cnt[c[r]]*cnt[c[r]];
cnt[c[r]]--;
temp=temp+cnt[c[r]]*cnt[c[r]];
r--;
}
//cout<<q[i].id<<endl;
ans[q[i].id].a=temp-(r-l+);
ans[q[i].id].b=(LL)(r-l+)*(r-l);
ans[q[i].id].simple();
}
} int main (){
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=;i<=n;i++){
scanf("%d",&c[i]);
}
for(int i=;i<=m;i++){
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(q+,q+m+,cmp);
memset(cnt,,sizeof(cnt));
solve();
for(int i=;i<=m;i++)
cout<<ans[i].a<<"/"<<ans[i].b<<endl;
}
return ;
}
入门题2： CF 86D Powerful array
http://codeforces.com/problemset/problem/86/D
题意：给你一个长度为n的数组，m个询问，每个询问需要你回答对于给出的区间【l，r】，sigma（cnt[v]*cnt[v]*v），其中v是【l，r】内的数字，cnt[v]是【l，r】内v的个数。
解法：区间的范围每移动一次，就可以在O(1)时间内完成更新，故可以使用莫队算法（具体实现详见代码）
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
using namespace std; typedef long long LL;
const int maxn=;
const int maxa=1e6; int n,t; struct node{
int l,r,id;
}q[maxn]; int cmp(const node& a,const node& b){
if(a.l/(int)sqrt(t)!=b.l/(int)sqrt(t)) return a.l/(int)sqrt(t)<b.l/(int)sqrt(t);
return a.r<b.r;
} int cnt[maxa+];
int a[maxn];
LL ans[maxn]; LL temp;
void update(int cur,int change){
temp-=(LL)cnt[a[cur]]*cnt[a[cur]]*a[cur];
cnt[a[cur]]+=change;
temp+=(LL)cnt[a[cur]]*cnt[a[cur]]*a[cur];
} void solve(){
temp=a[];
cnt[a[]]++;
int l=;
int r=;
for(int i=;i<=t;i++){
while(l<q[i].l){
update(l,-);
l++;
}
while(l>q[i].l){
l--;
update(l,);
}
while(r>q[i].r){
update(r,-);
r--;
}
while(r<q[i].r){
r++;
update(r,);
}
ans[q[i].id]=temp;
}
} int main (){
while(scanf("%d%d",&n,&t)!=EOF){
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=t;i++){
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(q+,q+t+,cmp);
memset(cnt,,sizeof(cnt));
solve();
for(int i=;i<=t;i++)
cout<<ans[i]<<endl;
}
return ;
}