Description:
作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……
具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。
Input:
输入文件第一行包含两个正整数N和M。N为袜子的数量，M为小Z所提的询问的数量。接下来一行包含N个正整数Ci，其中Ci表示第i只袜子的颜色，相同的颜色用相同的数字表示。再接下来M行，每行两个正整数L，R表示一个询问。
Output:
包含M行，对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1，否则输出的A/B必须为最简分数。（详见样例）
Sample Input:
| 1 2 3 4 5 6 | 6 4 1 2 3 3 3 2 2 6 1 3 3 5 1 6 |
Sample Output:
| 1 2 3 4 | 2/5 0/1 1/1 4/15 |
题解：
还是来做一做莫队算法的题目，其实该算法看上去极像暴力～
做过一道莫队套树状数组的题目再做这道题其实比较简单的～
代码如下：（貌似可以不用离散化）
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | /* ID: Sunshine_cfbsl PROG: BZOJ2038 LANG: C++ */ #include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int MAXN = 50010; int n, m, d, a[MAXN], Hash[MAXN]; int cnt, in[MAXN]; long long C[MAXN], ans[MAXN], f[MAXN]; struct Query { int l, r, id; bool operator < (const Query &rhs) const { return in[l] == in[rhs.l] ? r < rhs.r : in[l] < in[rhs.l]; } }q[MAXN]; inline int read() { int x = 0, f = 1; char ch = getchar(); for(; ch<'0' || ch>'9'; ch=getchar()) if(ch=='-') f=-1; for(; ch>='0'&&ch<='9'; ch=getchar()) x = x*10 + ch-'0'; return x * f; } long long gcd(long long a, long long b) { return b ? gcd(b, a%b) : a; } int main() { int i; n = read(), m = read(); for(i = 1; i <= n; i++) Hash[i] = a[i] = read(); sort(Hash+1, Hash+n+1); cnt = unique(Hash+1, Hash+n+1)-Hash-1; for(i = 1; i <= n; i++) a[i] = lower_bound(Hash+1, Hash+cnt+1, a[i])-Hash; d = sqrt(n); for(i = 1; i <= n; i++) in[i] = (i-1)/d+1; for(i = 1; i <= m; i++) { q[i].l = read(), q[i].r = read(); q[i].id = i, f[i] = (long long)(q[i].r-q[i].l+1)*(q[i].r-q[i].l); } sort(q+1, q+m+1); int l = 1, r = 0; long long res = 0; for(i = 1; i <= m; i++) { while(r < q[i].r) { r++, res += C[a[r]]*2, C[a[r]]++; } while(l < q[i].l) { res += -2*C[a[l]]+2, C[a[l]]--, l++; } while(r > q[i].r) { res += -2*C[a[r]]+2, C[a[r]]--, r--; } while(l > q[i].l) { l--, res += C[a[l]]*2, C[a[l]]++; } ans[q[i].id] = res; } for(i = 1; i <= m; i++) { if(ans[i] == 0) printf("0/1\n"); else { long long g = gcd(ans[i], f[i]); printf("%lld/%lld\n", ans[i]/g, f[i]/g); } } return 0; } |
