题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2038
题目：
题意：中文题意，大家都懂。
思路：莫队入门题。不过由于要去概率，所以我们假设询问区间内有k中物品，每种物品我们假设它的数量为pi。那么我们可以进行下面一系列的公式推导：
所以我们用莫队维护该区间内某颜色的平方和，对于最简分式我们用一个gcd即可求出。
代码实现如下：
1 #include <set> 2 #include <map> 3 #include <queue> 4 #include <stack> 5 #include <cmath> 6 #include <bitset> 7 #include <cstdio> 8 #include <string> 9 #include <vector> 10 #include <cstdlib> 11 #include <cstring> 12 #include <iostream> 13 #include <algorithm> 14 using namespace std; 15 16 typedef long long ll; 17 typedef unsigned long long ull; 18 19 #define bug printf("********* "); 20 #define FIN freopen("in.txt", "r", stdin); 21 #define debug(x) cout<<"["<<x<<"]" <<endl; 22 #define IO ios::sync_with_stdio(false),cin.tie(0); 23 24 const double eps = 1e-8; 25 const int mod = 1e9 + 7; 26 const int maxn = 5e4 + 7; 27 const double pi = acos(-1); 28 const int inf = 0x3f3f3f3f; 29 const ll INF = 0x3f3f3f3f3f3f3f3f; 30 31 int n, m, block; 32 ll sum; 33 int a[maxn], cnt[maxn]; 34 35 struct node { 36 int l, r, id; 37 ll ans1, ans2; 38 bool operator < (const node& x) const { 39 return (l - 1) / block == (x.l - 1) / block ? r < x.r : (l - 1) / block < (x.l - 1) / block; 40 } 41 }ask[maxn]; 42 43 void update (int p, int val) { 44 sum -= cnt[p] * cnt[p]; 45 cnt[p] += val; 46 sum += cnt[p] * cnt[p]; 47 } 48 49 ll gcd(ll a, ll b) { 50 return b == 0 ? a : gcd(b, a % b); 51 } 52 53 int main() { 54 //FIN; 55 while(~scanf("%d%d", &n, &m)) { 56 block = sqrt(n); 57 for(int i = 1; i <= n; i++) { 58 scanf("%d", &a[i]); 59 } 60 for(int i = 1; i <= m; i++) { 61 scanf("%d%d", &ask[i].l, &ask[i].r); 62 ask[i].id = i; 63 } 64 sort(ask + 1, ask + m + 1); 65 for(int i = 1, l = 1, r = 0; i <= m; i++) { 66 for(; r < ask[i].r; r++) update(a[r + 1], 1); 67 for(; r > ask[i].r; r--) update(a[r], -1); 68 for(; l < ask[i].l; l++) update(a[l], -1); 69 for(; l > ask[i].l; l--) update(a[l - 1], 1); 70 if(ask[i].l == ask[i].r) { 71 ask[ask[i].id].ans1 = 0, ask[ask[i].id].ans2 = 1; 72 continue; 73 } 74 ll k1 = sum - (ask[i].r - ask[i].l + 1); 75 ll k2 = (long long) (ask[i].r - ask[i].l + 1) * (ask[i].r - ask[i].l); 76 ll gg = gcd(k1, k2); 77 ask[ask[i].id].ans1 = k1 / gg; 78 ask[ask[i].id].ans2 = k2 / gg; 79 } 80 for(int i = 1; i <= m; i++) { 81 if(ask[i].ans1 == 0) { 82 printf("0/1 "); 83 } else { 84 printf("%lld/%lld ", ask[i].ans1, ask[i].ans2); 85 } 86 } 87 } 88 return 0; 89 }