基础莫队模板
记录一下莫队的板子
入门题 小z的袜子
#include <bits/stdc++.h>
#define int long long
#define endl '\\n'
#define sz(x) x.size()
#define lbt(x) (x)&(-x)
#define rep(i,n) for(int i=0;i<n;i++)using namespace std;typedef pair<int, int> PII;
typedef double db;
const int N = 5e4 + 10, mod = 998244353, inf = 0x3f3f3f3f;
const db EPS = 1e-9;
int res[N], a[N], id[N], cnt[N], len[N];
struct Q {int l, r, k;
}q[N];
int tmp;
void add(int x) {tmp += cnt[a[x]];cnt[a[x]]++;
}
void del(int x) {cnt[a[x]]--;tmp -= cnt[a[x]];
}
void solve() {int n, m;cin >> n >> m;int dk = sqrt(n);for (int i = 1;i <= n;i++) {id[i] = (i - 1) / dk + 1;cin >> a[i];}for (int i = 1;i <= m;i++) {int l, r;cin >> l >> r;len[i] = (r - l + 1) * (r - l) / 2;q[i] = { l,r,i };}sort(q + 1, q + 1 + m, [&](Q a, Q b) {if (id[a.l] == id[b.l])return a.r < b.r;return id[a.l] < id[b.l];});int l = 1, r = 0;for (int i = 1;i <= m;i++) {while (l > q[i].l) add(--l);while (r < q[i].r) add(++r);while (l < q[i].l) del(l++);while (r > q[i].r) del(r--);res[q[i].k] = tmp;}for (int i = 1;i <= m;i++) {int d = __gcd(res[i], len[i]);cout << res[i] / d << "/" << len[i] / d << endl;}
}signed main() {cin.tie(0)->sync_with_stdio(0);cout.tie(0);int _ = 1;// cin >> _ ;while (_--)solve();return 0;
}区间众数问题
2021 江西省赛 G Magic Number Group
#include <bits/stdc++.h>
// #define int long long
#define endl '\\n'
#define sz(x) x.size()
#define lbt(x) (x)&(-x)
#define rep(i,n) for(int i=0;i<n;i++)using namespace std;typedef pair<int, int> PII;
typedef double db;
const int N = 5e5 + 10, mod = 998244353, inf = 0x3f3f3f3f;
const db EPS = 1e-9;
int res[N], a[N], id[N], cnt[N], len[N], num[N];
vector<int>fac[N];
struct Q {int l, r, k;
}q[N];
int tmp, mx;
void init(int n) {for (int i = 1;i <= n;i++) fac[i].clear();
}
void work(vector<int>& v, int x) {for (int i = 2;i <= x / i;i++) {if (x % i)continue;while (x % i == 0)x /= i;v.push_back(i);}if (x > 1)v.push_back(x);
}
void add(int x) {for (auto t : fac[x]) {--num[cnt[t]], ++num[++cnt[t]];while (num[tmp + 1])tmp++;}
}
void del(int x) {for (auto t : fac[x]) {--num[cnt[t]], ++num[--cnt[t]];while (!num[tmp])tmp--;}
}
void solve() {int n, m;cin >> n >> m;init(n);int dk = sqrt(n);for (int i = 1;i <= n;i++) {id[i] = (i - 1) / dk + 1;cin >> a[i];work(fac[i], a[i]);}for (int i = 1;i <= m;i++) {int l, r;cin >> l >> r;len[i] = (r - l + 1) * (r - l) / 2;q[i] = { l,r,i };}sort(q + 1, q + 1 + m, [&](Q a, Q b) {if (id[a.l] == id[b.l])return a.r < b.r;return id[a.l] < id[b.l];});num[0] = 1;int l = 1, r = 0;for (int i = 1;i <= m;i++) {while (l > q[i].l) add(--l);while (r < q[i].r) add(++r);while (l < q[i].l) del(l++);while (r > q[i].r) del(r--);res[q[i].k] = tmp;}while (l <= r)del(r--);for (int i = 1;i <= m;i++) {cout << res[i] << endl;}
}signed main() {cin.tie(0)->sync_with_stdio(0);cout.tie(0);int _ = 1;cin >> _ ;while (_--)solve();return 0;
}
