P5268 [SNOI2017]一个简单的询问 题解

这里提供一个无脑分块做法。 看到数据范围 $5\times 10^4$，考虑分块，设块长为 $\sqrt n$。令 $sum_{i,j}$ 表示前 $j$ 个数对第 $i$ 个块产生的贡献。这个东西可以 $O(n\sqrt n)$ 预处理出来。 对于每个询问，把它拆成三个部分： - 区间二的所有整块 对 整个区间一 产生的贡献 - 区间一的所有整块 对 区间二的散块 产生的贡献 - 区间一的散块 对 区间二的散块 产生的贡献 建议自己画个图理解一下。 前两个部分显然可以直接利用 $sum$ 来搞，对于第三个部分，暴力开桶，扫一遍就没了。 时空复杂度均为 $O(n\sqrt n)$。常数较莫队略大，但不卡常也能做到稳定跑过。 ```cpp #include<bits/stdc++.h> using namespace std; const int maxn = 50005, maxb = 255; int n, m, block, t; int a[maxn], ind[maxn]; int sum[maxb][maxn]; int st[maxb], ed[maxb], pos[maxn]; int cnt[maxn]; void discrete() { memcpy(ind, a, sizeof(a)); sort(ind + 1, ind + 1 + n); int len = unique(ind + 1, ind + 1 + n) - ind - 1; for (int i = 1; i <= n; i++) a[i] = lower_bound(ind + 1, ind + 1 + n, a[i]) - ind; } void getsum(int k) { for (int i = st[k]; i <= ed[k]; i++) cnt[a[i]]++; for (int i = 1; i <= n; i++) sum[k][i] = sum[k][i - 1] + cnt[a[i]]; for (int i = st[k]; i <= ed[k]; i++) cnt[a[i]]--; } void init() { block = sqrt(n); t = ceil(n * 1. / block); for (int i = 1; i <= t; i++) { st[i] = (i - 1) * block + 1; ed[i] = min(i * block, n); for (int j = st[i]; j <= ed[i]; j++) pos[j] = i; } for (int i = 1; i <= t; i++) getsum(i); } int query(int l1, int r1, int l2, int r2) { int p1 = pos[l1], q1 = pos[r1], p2 = pos[l2], q2 = pos[r2], ans = 0; for (int i = p2 + 1; i <= q2 - 1; i++) ans += sum[i][r1] - sum[i][l1 - 1]; for (int i = p1 + 1; i <= q1 - 1; i++) if (p2 != q2) ans += sum[i][ed[p2]] - sum[i][l2 - 1] + sum[i][r2] - sum[i][st[q2] - 1]; else ans += sum[i][r2] - sum[i][l2 - 1]; if (p2 == q2) for (int i = l2; i <= r2; i++) cnt[a[i]]++; else { for (int i = l2; i <= ed[p2]; i++) cnt[a[i]]++; for (int i = st[q2]; i <= r2; i++) cnt[a[i]]++; } if (p1 == q1) for (int i = l1; i <= r1; i++) ans += cnt[a[i]]; else { for (int i = l1; i <= ed[p1]; i++) ans += cnt[a[i]]; for (int i = st[q1]; i <= r1; i++) ans += cnt[a[i]]; } if (p2 == q2) for (int i = l2; i <= r2; i++) cnt[a[i]]--; else { for (int i = l2; i <= ed[p2]; i++) cnt[a[i]]--; for (int i = st[q2]; i <= r2; i++) cnt[a[i]]--; } return ans; } int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; discrete(); init(); cin >> m; for (int i = 1; i <= m; i++) { int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2; cout << query(l1, r1, l2, r2) << endl; } return 0; } ```