简介

莫队二次离线由 lxl 最先提出，是莫队的一种变体，在转移复杂度较高时使用。

过程

对于一次转移，我们设该转移为从 $[l, r]$ 改变为 $[l, r + 1]$，其他转移同理。

将它拆为分别计算 $r + 1$ 对 $[1, r]$ 的贡献和对 $[1, l - 1]$ 的贡献，其中前者可以预处理求出。

对于后者，我们将所有它离线处理，然后像扫描线一样，从左向右扫，$n$ 次修改，$n\sqrt{m}$ 次查询（如果用可支持区间查的数据结构，则只需 $m$ 次查询）。

例题

Yuno loves sqrt technology II

简化题意：求允许离线的不带修区间逆序对，强制离线。

这里使用普通莫队只能做到 $O(n\sqrt{m}\log n)$ 的复杂度。

二次离线莫队过程如上，我们维护的数据结构为值域分块，做到修改 $O(\sqrt{n})$ 查询 $O(1)$，总复杂度 $O(n\sqrt{n})$。

详细过程见代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e5 + 10;
int n, m, B;
int a[N], s[N], s2[N];
ll sum1[N], sum2[N], ans[N];

struct Query {
    int l, r, id;
};

struct QQ {
    int l, r, k, id, f;
};

struct Tree {
    int tr[N];
    void add(int x, int k) {while (x <= n) {tr[x] += k; x += x & -x;}}
    int qry(int x) {int res = 0; while (x) {res += tr[x]; x -= x & -x;} return res;}
} T1;

/* 用树状数组预处理 */

vector<QQ> Q1, Q2;

bool cmp(Query AA, Query BB) { return (AA.l / B != BB.l / B) ? (AA.l < BB.l) : (AA.r < BB.r);} // 莫队排序
bool cmp2(QQ AA, QQ BB) {return AA.k < BB.k;} // 二次离线

void solve1() { // 计算第一类
    sort(Q1.begin(), Q1.end(), cmp2);
    int j = Q1.size() - 1;
    while (j >= 0 && Q1[j].k == n + 1) j -- ;
    for (int i = n; i >= 1; i -- ) {
        int r = n + 1;
        for (int k = n / B; k * B >= a[i] + 1; k -- ) s2[k] ++ , r = k * B;
        for (int k = a[i] + 1; k < r; k ++ ) s[k] ++ ;
        while (j >= 0 && Q1[j].k == i) {
            for (int k = Q1[j].l; k <= Q1[j].r; k ++ ) ans[Q1[j].id] += Q1[j].f * (s[a[k]] + s2[a[k] / B]);
            j -- ;
        }
    }
}

void solve2() { // 计算第二类
    memset(s, 0, sizeof s);
    memset(s2, 0, sizeof s2);
    sort(Q2.begin(), Q2.end(), cmp2);
    int j = 0;
    while (j < Q2.size() && Q2[j].k == 0) j ++ ;
    for (int i = 1; i <= n; i ++ ) {
        int l = 1;
        for (int k = 0; (k + 1) * B - 1 < a[i]; k ++ ) s2[k] ++ , l = (k + 1) * B;
        for (int k = l; k < a[i]; k ++ ) s[k] ++ ;
        while (j < Q2.size() && Q2[j].k == i) {
            for (int k = Q2[j].l; k <= Q2[j].r; k ++ ) ans[Q2[j].id] += Q2[j].f * (s[a[k]] + s2[a[k] / B]);
            j ++ ;
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    B = (int)sqrt(n);

    vector<pair<int, int>> bb;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]), bb.push_back({a[i], i});
    sort(bb.begin(), bb.end());
    for (int i = 0; i < n; i ++ ) a[bb[i].second] = i + 1;

    for (int i = 1; i <= n; i ++ ) sum1[i] = sum1[i - 1] + T1.qry(n) - T1.qry(a[i]), T1.add(a[i], 1);
    for (int i = 1; i <= n; i ++ ) T1.add(a[i], -1);
    for (int i = n; i >= 1; i -- ) sum2[i] = sum2[i + 1] + T1.qry(a[i] - 1), T1.add(a[i], 1);

    vector<Query> Q(m);
    for (int i = 0; i < m; i ++ ) {
        int l, r;
        scanf("%d%d", &l, &r);
        Q[i] = {l, r, i};
    }

    sort(Q.begin(), Q.end(), cmp);
    for (int k = 0, i = 1, j = 0; k < m; k ++ ) {
        int l = Q[k].l, r = Q[k].r, id = Q[k].id;
        if (i > l) ans[id] += sum2[l] - sum2[i], Q1.push_back({l, i - 1, j + 1, id, -1}), i = l;
        if (j < r) ans[id] += sum1[r] - sum1[j], Q2.push_back({j + 1, r, i - 1, id, -1}), j = r;
        if (i < l) ans[id] -= sum2[i] - sum2[l], Q1.push_back({i, l - 1, j + 1, id, 1}), i = l;
        if (j > r) ans[id] -= sum1[j] - sum1[r], Q2.push_back({r + 1, j, i - 1, id, 1}), j = r;
    }

    solve1(); solve2();
    for (int i = 1; i < m; i ++ ) ans[Q[i].id] += ans[Q[i - 1].id];
    for (int i = 0; i < m; i ++ ) printf("%lld\n", ans[i]);

    return 0;
}