跳转至

莫队二次离线

例题 1

Luogu P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II

给你一个长为 的序列 ， 次询问，每次查询一个区间的逆序对数。

数据范围：，。

查询区间逆序对数，在使用莫队的同时维护一颗权值线段树或权值树状数组，可以在 的时间复杂度内解决该问题。当然，取块长 更优。

可是这样的复杂度仍然无法达到毒瘤出题人的要求，我们需要在此算法上进一步优化。

考虑该题与其它使用莫队的题的差异性，由于需要在维护值域的数据结构上查询，故单次端点的移动是 而非 。

众所周知，莫队是一种离线算法，它通过将询问离线处理的方式来优化复杂度。我们在将原问题的查询离线的基础上，尝试将端点移动时在数据结构上进行的修改和查询操作离线下来统一处理，最后用 的时间复杂度解决问题。由于前后进行了两次离线操作，故称为「莫队二次离线」。

例题 2

Luogu P5501 [LnOI2019] 来者不拒，去者不追

给定一个长度为 的序列 。给定 个询问，每次询问一个区间中 中所有数的「Abbi 值」之和。

Abbi 值定义为：若 在询问区间 中是第 小，那么它的「Abbi 值」等于 。

数据范围：，，。

示例代码 
#include <algorithm>
#include <iostream>
#include <vector>

using lxl = long long;

constexpr int MAXN = 5e5;
constexpr int MAXM = 5e5;
constexpr int MAXA = 1e5;
constexpr int sqrN = 708;
constexpr int sqrA = 317;

int n, m;
int a[MAXN + 10];
int b[MAXN + 10];
int l, r;
lxl f[MAXN + 10];
lxl g[MAXN + 10];
lxl ans[MAXM + 10];

struct SegmentTree {
  struct Node {
    lxl val;
    lxl tag;
  } node[4 * MAXA + 10];

  void MakeTag(int u, int l, int r, lxl val) {
    node[u].val += val * (r - l + 1);
    node[u].tag += val;
    return;
  }

  void PushDown(int u, int l, int r) {
    if (!node[u].tag) return;
    int mid = (l + r) / 2;
    MakeTag(2 * u, l, mid, node[u].tag);
    MakeTag(2 * u + 1, mid + 1, r, node[u].tag);
    node[u].tag = 0;
    return;
  }

  void PushUp(int u) {
    node[u].val = node[2 * u].val + node[2 * u + 1].val;
    return;
  }

  void Add(int u, int l, int r, int s, int t, lxl val) {
    if (s > t) return;
    if (s <= l && r <= t) {
      MakeTag(u, l, r, val);
      return;
    }
    PushDown(u, l, r);
    int mid = (l + r) / 2;
    if (s <= mid) Add(2 * u, l, mid, s, t, val);
    if (t >= mid + 1) Add(2 * u + 1, mid + 1, r, s, t, val);
    PushUp(u);
    return;
  }

  void Add(int u, int l, int r, int pos, lxl val) {
    Add(u, l, r, pos, pos, val);
    return;
  }

  lxl Ask(int u, int l, int r, int s, int t) {
    if (s > t) return 0;
    if (s <= l && r <= t) {
      return node[u].val;
    }
    PushDown(u, l, r);
    int mid = (l + r) / 2;
    if (t <= mid) return Ask(2 * u, l, mid, s, t);
    if (s >= mid + 1) return Ask(2 * u + 1, mid + 1, r, s, t);
    return Ask(2 * u, l, mid, s, t) + Ask(2 * u + 1, mid + 1, r, s, t);
  }
};

using sgt = SegmentTree;

struct BlockArray {
  struct Block {
    int l, r;
    lxl tag;
  } block[sqrA + 10];

  struct Array {
    int bel;
    lxl val;
  } array[MAXA + 10];

  void Build() {
    for (int i = 1; i <= MAXA; i++) array[i].bel = (i - 1) / sqrA + 1;
    for (int i = 1; i <= MAXA; i++) block[array[i].bel].r = i;
    for (int i = MAXA; i >= 1; i--) block[array[i].bel].l = i;
    return;
  }

  void Add(int pos, lxl val) {
    for (int i = array[pos].bel + 1; i <= array[MAXA].bel; i++)
      block[i].tag += val;
    for (int i = pos; i <= block[array[pos].bel].r; i++) array[i].val += val;
    return;
  }

  lxl Ask(int pos) { return array[pos].val + block[array[pos].bel].tag; }

  lxl Ask(int l, int r) {
    if (l > r) return 0;
    return Ask(r) - Ask(l - 1);
  }
};

using dba = BlockArray;

namespace captainMoSecondaryOffline {
namespace offline2 {
struct Query {
  int i;
  int l, r;
  int k;
};

std::vector<Query> query[MAXN + 10];

dba sum, cnt;

void solve() {
  sum.Build();
  cnt.Build();
  for (int i = 1; i <= n; i++) {
    sum.Add(a[i], a[i]);
    cnt.Add(a[i], 1);
    for (int j = 0; j < query[i].size(); j++) {
      for (int k = query[i][j].l; k <= query[i][j].r; k++) {
        ans[query[i][j].i] +=
            1ll * query[i][j].k *
            (sum.Ask(a[k] + 1, MAXA) + cnt.Ask(1, a[k] - 1) * a[k]);
      }
    }
  }
  return;
}
}  // namespace offline2

namespace offline1 {
struct Query {
  int i;
  int l, r;

  bool operator<(const Query &other) const {
    if (b[l] != b[other.l]) return l < other.l;
    return r < other.r;
  }
};

std::vector<Query> query;

sgt sum, cnt;

void solve() {
  std::sort(query.begin(), query.end());
  for (int i = 1; i <= n; i++) {
    f[i] = sum.Ask(1, 1, MAXA, a[i] + 1, MAXA);
    g[i] = cnt.Ask(1, 1, MAXA, 1, a[i] - 1);
    sum.Add(1, 1, MAXA, a[i], a[i]);
    cnt.Add(1, 1, MAXA, a[i], 1);
  }
  for (int i = 0, l = 1, r = 0; i < query.size(); i++) {
    if (l > query[i].l) {
      offline2::query[r].push_back(
          offline2::Query{query[i].i, query[i].l, l - 1, 1});
      while (l > query[i].l) {
        l--;
        ans[query[i].i] -= f[l] + (g[l] - 1) * a[l];
      }
    }
    if (r < query[i].r) {
      offline2::query[l - 1].push_back(
          offline2::Query{query[i].i, r + 1, query[i].r, -1});
      while (r < query[i].r) {
        r++;
        ans[query[i].i] += f[r] + (g[r] + 1) * a[r];
      }
    }
    if (l < query[i].l) {
      offline2::query[r].push_back(
          offline2::Query{query[i].i, l, query[i].l - 1, -1});
      while (l < query[i].l) {
        ans[query[i].i] += f[l] + (g[l] - 1) * a[l];
        l++;
      }
    }
    if (r > query[i].r) {
      offline2::query[l - 1].push_back(
          offline2::Query{query[i].i, query[i].r + 1, r, 1});
      while (r > query[i].r) {
        ans[query[i].i] -= f[r] + (g[r] + 1) * a[r];
        r--;
      }
    }
  }
  return;
}
}  // namespace offline1

void solve() {
  offline1::solve();
  offline2::solve();
  for (int i = 1; i < m; i++)
    ans[offline1::query[i].i] += ans[offline1::query[i - 1].i];
  return;
}
}  // namespace captainMoSecondaryOffline

int main() {
  std::cin >> n >> m;
  for (int i = 1; i <= n; i++) std::cin >> a[i];
  for (int i = 1; i <= n; i++) b[i] = (i - 1) / sqrN + 1;
  for (int i = 1; i <= m; i++) {
    std::cin >> l >> r;
    captainMoSecondaryOffline::offline1::query.push_back(
        captainMoSecondaryOffline::offline1::Query{i, l, r});
  }
  captainMoSecondaryOffline::solve();
  for (int i = 1; i <= m; i++) std::cout << ans[i] << '\n';
  return 0;
}
最后更新: 2023年9月24日
创建日期: 2023年5月26日
回到页面顶部