莫队也是暴力的一种，不过可以很有效的降低复杂度
如果我们已知[l, r]的答案，能在O(1)时间得到[l+1,r]的答案以及[l, r-1]的答案，即可使用莫队算法。
时间复杂度为O(n^1.5)。如果只能在logn的时间移动区间，则时间复杂度是O(n^1.5*logn)
也就是说如果已知[l, r]的答案，要求[l', r']的答案，我们可以通过|l – l'|+|r – r'|次转移内求得
一般来讲先分块，然后一块一块的求解（分块：http://blog.csdn.net/jaihk662/article/details/64508903）
求出每个询问的l落入第几块（pos[l]表示l在第pos[l]块），r不变
然后按pos[l]优先级排序，如果pos[l]相同，再按r排序
之后依次暴力就好了，也就是不停的进行|l – l'|+|r – r'|转移
复杂度O(n^1.5)
在同一个块里，总体的r最多移动n次，l最多移动sqrt(n)次，所以每一块的复杂度都是n+sqrt(n)==O(n)
然后总共有sqrt(n)块，所以总复杂度就是O(n^1.5)
作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命…… 具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。 你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。
输入文件第一行包含两个正整数N和M。N为袜子的数量，M为小Z所提的询问的数量。接下来一行包含N个正整数Ci，其中Ci表示第i只袜子的颜色，相同的颜色用相同的数字表示。再接下来M行，每行两个正整数L，R表示一个询问。
包含M行，对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1，否则输出的A/B必须为最简分数。（详见样例）
这题如何进行O(1)的转移呢？
令sum[i]表示区间内第i中颜色的袜子个数，那么有
所以你只需要O(1)修改sum[i]²就好了
#include<stdio.h> #include<math.h> #include<string.h> #include<algorithm> using namespace std; #define LL long long typedef struct { LL l, r, id; LL p, q; }Res; Res s[50005]; LL ans, c[50005], pos[50005], val[50005]; bool comp1(Res a, Res b) { if(pos[a.l]==pos[b.l]) { if(a.r<b.r) return 1; return 0; } if(a.l<b.l) return 1; return 0; } bool comp2(Res a, Res b) { if(a.id<b.id) return 1; return 0; } LL Gcd(LL a, LL b) { if(b==0) return a; return Gcd(b, a%b); } void Update(LL x, LL t) { ans -= val[c[x]]*val[c[x]]; val[c[x]] += t; ans += val[c[x]]*val[c[x]]; } int main(void) { LL i, l, r, n, m, block, k; while(scanf("%lld%lld", &n, &m)!=EOF) { for(i=1;i<=n;i++) scanf("%lld", &c[i]); for(i=1;i<=m;i++) { scanf("%lld%lld", &s[i].l, &s[i].r); s[i].id = i; } block = sqrt(n); for(i=1;i<=n;i++) pos[i] = (i-1)/block+1; sort(s+1, s+m+1, comp1); l = 1, r = 0; memset(val, 0, sizeof(val)); ans = 0; for(i=1;i<=m;i++) { while(r<s[i].r) r++, Update(r, 1); while(r>s[i].r) Update(r, -1), r--; while(l<s[i].l) Update(l, -1), l++; while(l>s[i].l) l--, Update(l, 1); if(s[i].l==s[i].r) { s[i].p = 0; s[i].q = 1; continue; } s[i].p = ans-(s[i].r-s[i].l+1); s[i].q = (s[i].r-s[i].l+1)*(s[i].r-s[i].l); k = Gcd(s[i].p, s[i].q); s[i].p /= k; s[i].q /= k; } sort(s+1, s+m+1, comp2); for(i=1;i<=m;i++) printf("%lld/%lld\n", s[i].p, s[i].q); } return 0; }
