题目链接：点击打开链接
题意：给n个袜子， 每个袜子有一个颜色。 m次查询，每次查询给一个区间， 求在区间里的任选一对袜子的颜色相同的概率。
最经典的莫队算法， 莫队算法有两种， 我刚刚学了第一种：分块。
简单来说，假设总区间长度为n，那么将区间分成size = sqrt(n)块，那么每一块的长度为n/size，也是sqrt(n)，所以每次只维护一块里的内容和块与块之间的内容，如果改变一个数的值，那么只需要改变其所在的那一块就行了，最多遍历sqrt(n)次，如果要进行区间查询，那么首先要遍历完全在区间中的每一块的信息，复杂度最高O(sqrt(n))， 然后遍历在两边的不完全被包含的部分，也是sqrt(n)，所以总的复杂度就是O(sqrt(n))。
细节参见代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int mod = 1000000000 + 7;
const int INF = 1000000000;
const int maxn = 50010;
int T,n,m,unit,a[maxn];
ll vis[maxn];
struct node {
int l, r, id;
bool operator < (const node& rhs) const {
if(l/unit != rhs.l/unit) return l/unit < rhs.l/unit;
else return r/unit < rhs.r/unit;
}
}node[maxn];
struct Ans {
ll a, b;
}ans[maxn];
ll gcd(ll a, ll b) {
if(b == 0) return a;
return gcd(b, a%b);
}
void solve() {
ll cur = 0;
memset(vis, 0, sizeof(vis));
int l = 1, r = 0;
for(int i=0;i<m;i++) {
int L = node[i].l, R = node[i].r;
while(r < R) {
r++;
cur -= (ll)vis[a[r]] * (vis[a[r]]-1);
vis[a[r]]++;
cur += (ll)vis[a[r]] * (vis[a[r]]-1);
}
while(r > R) {
cur -= (ll)vis[a[r]] * (vis[a[r]]-1);
vis[a[r]]--;
cur += (ll)vis[a[r]] * (vis[a[r]]-1);
r--;
}
while(l < L) {
cur -= (ll)vis[a[l]] * (vis[a[l]]-1);
vis[a[l]]--;
cur += (ll)vis[a[l]] * (vis[a[l]]-1);
l++;
}
while(l > L) {
l--;
cur -= (ll)vis[a[l]] * (vis[a[l]]-1);
vis[a[l]]++;
cur += (ll)vis[a[l]] * (vis[a[l]]-1);
}
ll len = r - l + 1;
ans[node[i].id].a = cur;
ans[node[i].id].b = len * (len-1);
ll g = gcd(ans[node[i].id].a,ans[node[i].id].b);
ans[node[i].id].a /= g;
ans[node[i].id].b /= g;
}
}
int main() {
while(~scanf("%d%d",&n,&m)) {
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
}
for(int i=0;i<m;i++) {
scanf("%d%d",&node[i].l,&node[i].r);
node[i].id = i;
}
unit = floor(sqrt(n));
sort(node, node+m);
solve();
for(int i=0;i<m;i++) {
printf("%lld/%lld\n",ans[i].a,ans[i].b);
}
}
return 0;
}
BZOJ 2038: [2009国家集训队]小Z的袜子(hose)（莫队算法）
原文：http://blog.csdn.net/weizhuwyzc000/article/details/50579909