- 前言
- 简介：优雅的暴力
- 普通莫队
- 题目1：询问区间不同数的个数&普通莫队&（主席树||线段树||树状数组也都可以解决）&不要吝啬空间（所有数组都1e7+5都没问题，只要不MLE）
- 拓展题目1：查询区间 [ l , r ] [l,r] [l,r]的 ∑ i = 1 i = k c [ i ] 2 sum_{i=1}^{i=k}c[i]^2 ∑i=1i=kc[i]2，其中 c [ i ] c[i] c[i]表示值为 i i i的个数。
- 参考资料：
- 引入&普通莫队：【算法讲堂】【电子科技大学】【ACM】莫队算法
- 莫队算法可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。
- 只能应用于离线，强制在线（上一次询问的答案，作为下一次询问的内容。即这一次询问的内容，比如用到上一次询问的答案）的话就不能用莫队。
- 分类：
- 普通莫队
- 树上莫队
- 带修改莫队
-
题型：能够 O ( 1 ) O(1) O(1)转移就能用普通莫队。
-
原理：优雅暴力
- 怎样优化的：关键是排序。
- 怎样优化的：关键是排序。
- 传送门：D-query SPOJ - DQUERY
- 题意：给定一个长度为
n
n
n的数组
a
a
a，
q
q
q次询问，每次询问区间
[
l
i
,
r
i
]
[l_i,r_i]
[li,ri]，要求输出区间
[
l
i
,
r
i
]
[l_i,r_i]
[li,ri]内不同数的个数。
- 1 ≤ n ≤ 3 e 4 1le nle 3e4 1≤n≤3e4
- 1 ≤ a i ≤ 1 e 6 1le a_ile 1e6 1≤ai≤1e6
- 1 ≤ q ≤ 2 e 5 1le qle 2e5 1≤q≤2e5
- 1 ≤ l i ≤ r i ≤ n 1le l_ile r_ile n 1≤li≤ri≤n
- 题解：查询区间
[
l
,
r
]
[l,r]
[l,r]
- 主席树和线段树/树状数组的题解：同一个数都只记录最后位置（标记为1），其他位置标记为0。
- 主席树：查询第 r r r棵线段树的区间 [ l , r ] [l,r] [l,r]的和即可。
- 线段树/树状数组：也是离线处理， r r r为第一关键字进行排序，一直更新到 r r r然后查询区间 [ l , r ] [l,r] [l,r]的和即可。
- 莫队：就没多少思维难度了。
- 维护任意状态 [ L , R ] [L,R] [L,R]，然后暴力更新即可。
- 排序是关键：如果 l l l在同一块，那就按 r r r从小到大排序，否则就按 l l l从小到大排序。——复杂度分析：因为可以 O ( 1 ) O(1) O(1)更新，所以移动次数即为复杂度， l l l最多移动 n ∗ n n*sqrt{n} n∗n 次， r r r最多也是移动 n ∗ n n*sqrt{n} n∗n 次，所以复杂度是 O ( n ∗ n ) O(n*sqrt{n}) O(n∗n )级别的。
- 主席树和线段树/树状数组的题解：同一个数都只记录最后位置（标记为1），其他位置标记为0。
- 代码：
#include拓展题目1：查询区间 [ l , r ] [l,r] [l,r]的 ∑ i = 1 i = k c [ i ] 2 sum_{i=1}^{i=k}c[i]^2 ∑i=1i=kc[i]2，其中 c [ i ] c[i] c[i]表示值为 i i i的个数。// #define int long long using namespace std; template void read(T &x) { T res = 0, f = 1; char c = getchar(); while (!isdigit(c)) { if (c == '-') f = -1; c = getchar(); } while (isdigit(c)) res = (res << 3) + (res << 1) + (c - '0'), c = getchar(); x = res * f; } const int N = 1e7 + 5; int n, a[N], q; int id[N], st[N], ed[N], block; int cnt[N], nowans = 0; int ans[N]; struct node { int l, r, i; bool operator<(const node &b) const { if (id[l] == id[b.l]) return r < b.r; else return id[l] < id[b.l]; } } s[N]; void init_block(int n) { block = sqrt(n); for (int i = 1; i <= block; i++) st[i] = n / block * (i - 1) + 1, ed[i] = n / block * i; ed[block] = n; for (int i = 1; i <= block; i++) for (int j = st[i]; j <= ed[i]; j++) id[j] = i; } void update(int x, int k) { if (k == 1) { if (cnt[a[x]] == 0) nowans++; cnt[a[x]]++; } else { cnt[a[x]]--; if (cnt[a[x]] == 0) nowans--; } } signed main() { read(n); for (int i = 1; i <= n; i++) read(a[i]); read(q); for (int i = 1; i <= q; i++) read(s[i].l), read(s[i].r), s[i].i = i; init_block(n); sort(s + 1, s + 1 + q); // int L = 1, R = n; // for (int i = L; i <= R; i++) update(i, 1); int L = 0, R = 0; //虽然任意区间都ok，但是上面复杂度还会大一点->但是上面不会出现负数的情况->但是出现负数好像也没事，而且上面也是可能出现负数的 for (int i = 1; i <= q; i++) { while (L < s[i].l) update(L++, -1); while (L > s[i].l) update(--L, 1); //注意加减 while (R > s[i].r) update(R--, -1); while (R < s[i].r) update(++R, 1); ans[s[i].i] = nowans; } for (int i = 1; i <= q; i++) printf("%dn", ans[i]); return 0; }
- 传送门：P2709 小B的询问
- 提示：能O(1)转移->也是普通莫队模板题。
