差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:各季度训练计划及训练记录:普通莫队算法_lgwza [2020/08/03 23:23]
lgwza 创建
+++ 2020-2021:teams:legal_string:各季度训练计划及训练记录:普通莫队算法_lgwza [2020/08/03 23:26] (当前版本)
lgwza [普通莫队的优化]
@@ 行 66: / 行 66: @@
 **注意：由于 ''%%++l%%'' 和 ''%%--r%%'' 的存在，下面代码中的移动区间的 4 个 for 循环的位置很关键，不能改变它们之间的位置关系。**
+参考代码：
+<hidden>
+<code cpp>
+#include <algorithm>
+#include <cmath>
+#include <cstdio>
+using namespace std;
+const int N = 50005;
+int n, m, maxn;
+int c[N];
+long long sum;
+int cnt[N];
+long long ans1[N], ans2[N];
+struct query {
+  int l, r, id;
+  bool operator<(const query &x) const {
+    if (l / maxn != x.l / maxn) return l < x.l;
+    return (l / maxn) & 1 ? r < x.r : r > x.r;
+  }
+} a[N];
+void add(int i) {
+  sum += cnt[i];
+  cnt[i]++;
+}
+void del(int i) {
+  cnt[i]--;
+  sum -= cnt[i];
+}
+long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
+int main() {
+  scanf("%d%d", &n, &m);
+  maxn = sqrt(n);
+  for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
+  for (int i = 0; i < m; i++) scanf("%d%d", &a[i].l, &a[i].r), a[i].id = i;
+  sort(a, a + m);
+  for (int i = 0, l = 1, r = 0; i < m; i++) {
+    if (a[i].l == a[i].r) {
+      ans1[a[i].id] = 0, ans2[a[i].id] = 1;
+      continue;
+    }
+    while (l < a[i].l) del(c[l++]);
+    while (l > a[i].l) add(c[--l]);
+    while (r < a[i].r) add(c[++r]);
+    while (r > a[i].r) del(c[r--]);
+    ans1[a[i].id] = sum;
+    ans2[a[i].id] = (long long)(r - l + 1) * (r - l) / 2;
+  }
+  for (int i = 0; i < m; i++) {
+    if (ans1[i] != 0) {
+      long long g = gcd(ans1[i], ans2[i]);
+      ans1[i] /= g, ans2[i] /= g;
+    } else
+      ans2[i] = 1;
+    printf("%lld/%lld\n", ans1[i], ans2[i]);
+  }
+  return 0;
+}
+</code>
+</hidden>
+===== 普通莫队的优化 =====
+我们看一下下面这组数据
+<code>
+// 设块的大小为 2 (假设)
+1
+100
+1
+100
+</code>
+手动模拟一下可以发现，r 指针的移动次数大概为 300 次，我们处理完第一个块之后，$l=2,r=100$，此时只需移动两次 l 指针就可以得到第四个询问的答案，但是我们却将 r 指针移动到 1 来获取第三个询问的答案，再移动到 100 获取第四个询问的答案，这样多了九十几次的指针移动。我们怎么优化这个地方呢？这里我们就要用到奇偶化排序。
+什么是奇偶化排序？奇偶化排序即对于属于奇数块的询问，r 按从小到大排序，对于属于偶数块的排序，r 从大到小排序，这样我们的 r 指针在处理完这个奇数块的问题后，将在返回的途中处理偶数块的问题，再向 n 移动处理下一个奇数块的问题，优化了 r 指针的移动次数，一般情况下，这种优化能让程序快 30% 左右。
+排序代码：
+压行
+<code cpp>
+// 这里有个小细节等下会讲
+int unit;  // 块的大小
+struct node {
+  int l, r, id;
+  bool operator<(const node &x) const {
+    return l / unit == x.l / unit
+               ? (r == x.r ? 0 : ((l / unit) & 1) ^ (r < x.r))
+               : l < x.l;
+  }
+};
+</code>
+不压行
+<code cpp>
+struct node {
+  int l, r, id;
+  bool operator<(const node &x) const {
+    if (l / unit != x.l / unit) return l < x.l;
+    if ((l / unit) & 1)
+      return r <
+             x.r;  // 注意这里和下面一行不能写小于（大于）等于，否则会出错（详见下面的小细节）
+    return r > x.r;
+  }
+};
+</code>
+> 小细节：如果使用 sort 比较两个函数，不能出现 $a<b$ 和 $b<a$ 同时为真的情况，否则会运行错误。
+对于压行版，如果没有 ''%%r == x.r%%'' 的特判，当 l 属于同一奇数块且 r 相等时，会出现上面小细节中的问题（自己手动模拟一下），对于压行版，如果写成小于（大于）等于，则也会出现同样的问题。
+===== 参考链接 =====
+[[https://oi-wiki.org/misc/mo-algo/|OI Wiki]]

CVBB ACM Team

用户工具

站点工具

差别

页面工具