Description

給定序列 $a=(a_1,a_2,?,a_n)$，有 $q$ 次查詢，每次查詢給定 $(l,r)$.
你需要求出 $\frac{2{\sum }_{i\le i<j\le r}[a_i=a_j]}{(r?l)(r?l+1)}$，以最簡分數形式輸出.

Limitations

$1\le n,m\le 5\times 10^4$
$1\le l\le r\le n$
$1\le a_i\le n$
$0.2\text{s},128\text{MB}$

Solution

這種不好直接維護的題，考慮上莫隊.
我們設 $cn{t}_i$ 為當前區間內 $i$ 的出現次數.
那么，這 $cn{t}_i$ 個 $i$ 可以兩兩配成滿足條件的對，其對分子的貢獻顯然為 ${\text{cnt}}_i\times ({\text{cnt}}_i?1)$.
在 add 和 del 時，先將原來 $a_x$ 的貢獻減掉，更新 $\text{cnt}$ 后再加回去.
剩下的就是是模板，但有幾個坑：

• 分子和分母會爆 int，要開 long long.
• 注意特判 $l=r$.
• 調塊長，實測取 $B=\sqrt{n}$ 可以過.

Code

$2.41\text{KB},0.35\text{s},2.17\text{MB}\text{(in?total,?C++20?with?O2)}$

#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}namespace fastio {}   // Removed
using fastio::read;
using fastio::write;struct Query { int l, r, id;inline Query() {}inline Query(int _l, int _r, int _id) : l(_l), r(_r), id(_id) {}
}; signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);const int n = read<int>(), m = read<int>();const int B = sqrt(n);vector<int> c(n);for (int i = 0; i < n; i++) c[i] = read<int>(), c[i]--;i64 res = 0;vector<int> cnt(n);auto f = [&](int x) { return 1LL * x * (x - 1) / 2; };auto upd = [&](int x, int k) {res -= f(cnt[c[x]]);cnt[c[x]] += k;res += f(cnt[c[x]]);};vector<Query> qry(m);for (int i = 0, l, r; i < m; i++) {l = read<int>(), r = read<int>(), l--, r--;qry[i] = Query(l, r, i);}sort(qry.begin(), qry.end(), [&](const Query& a, const Query& b) {return (a.l / B == b.l / B) ? (a.r / B < b.r / B) : (a.l / B < b.l / B);});int l = 0, r = -1;vector<i64> num(m), den(m);for (auto& [ql, qr, id] : qry) {while (ql < l) upd(--l, 1);while (r < qr) upd(++r, 1);while (l < ql) upd(l++, -1);while (qr < r) upd(r--, -1);const i64 a = res, b = f(qr - ql + 1), g = gcd(a, b);if (a == 0) num[id] = 0, den[id] = 1;else num[id] = a / g, den[id] = b / g;}for (int i = 0; i < m; i++) {write(num[i]), putchar_unlocked('/');write(den[i]), putchar_unlocked('\n');}return 0;
}