题意：在[l, r]之中任选两个数，求它们相同的概率。
解：
莫队入门。
概率这个很好搞，就是cnt * (cnt - 1) / 2。
然后发现每次挪指针的时候，某一个cnt会+1或-1。这时候差值就是2 * cntsmall。
1 #include2 #include 3 #include 4 5 typedef long long LL; 6 const int N = 50010; 7 8 int a[N], bin[N], fr[N]; 9 LL ans;10 11 struct ASK {12 int id, l, r;13 LL ans;14 inline bool operator <(const ASK &w) const {15 if(fr[l] != fr[w.l]) {16 return fr[l] < fr[w.l];17 }18 return r < w.r;19 }20 }ask[N];21 22 inline bool cmp(const ASK &a, const ASK &b) {23 return a.id < b.id;24 }25 26 inline LL gcd(LL a, LL b) {27 if(!b) {28 return a;29 }30 return gcd(b, a % b);31 }32 33 inline void add(int x) {34 ans += bin[a[x]] << 1;35 bin[a[x]]++;36 return;37 }38 39 inline void del(int x) {40 bin[a[x]]--;41 ans -= bin[a[x]] << 1;42 }43 44 int main() {45 int n, m;46 scanf("%d%d", &n, &m);47 int T = sqrt(n);48 for(int i = 1; i <= n; i++) {49 scanf("%d", &a[i]);50 fr[i] = (i - 1) / T + 1;51 }52 for(int i = 1; i <= m; i++) {53 ask[i].id = i;54 scanf("%d%d", &ask[i].l, &ask[i].r);55 }56 std::sort(ask + 1, ask + m + 1);57 58 int L = 1, R = 1;59 bin[a[1]]++;60 for(int i = 1; i <= m; i++) {61 if(ask[i].l == ask[i].r) {62 continue;63 }64 while(ask[i].l < L) {65 add(--L);66 }67 while(R < ask[i].r) {68 add(++R);69 }70 while(L < ask[i].l) {71 del(L++);72 }73 while(ask[i].r < R) {74 del(R--);75 }76 ask[i].ans = ans;77 }78 79 std::sort(ask + 1, ask + m + 1, cmp);80 for(int i = 1; i <= m; i++) {81 if(!ask[i].ans || ask[i].l == ask[i].r) {82 puts("0/1");83 continue;84 }85 int g = gcd(ask[i].ans, 1ll * (ask[i].r - ask[i].l + 1) * (ask[i].r - ask[i].l));86 printf("%lld/%lld\n", ask[i].ans / g, 1ll * (ask[i].r - ask[i].l + 1) * (ask[i].r - ask[i].l) / g);87 }88 return 0;89 }