跳转至

莫队二次离线

有些题目不易在线 update(pos, w)（扩展和删除）。由于莫队算法的确定性，我们可以将所有 update(pos, w) 离线下来，通过某些离线算法求得每次 update 的贡献。

由于 update 调用的总次数是 \(O(n\sqrt n)\) 的，因此要求第二次离线必须实现 \(O(1)\) 查询。

通过某些技巧，我们还可以将空间复杂度降低到 \(O(n)\)。

用法

莫队二次离线通常用来解决一类问题：统计区间 \([l,r]\) 中满足条件的数对 \((a_i,a_j)\) 的数量。

莫队二次离线降低时间复杂度的核心是：通过离线并差分，将区间转化为前缀，从而将修改操作数量降低为序列长度 \(n\) 级别，然后通过平衡法实现 \(O(1)\) 查询。

因此，使用莫队二次离线有以下几个条件：

  • 使用普通莫队无法实现 \(O(1)\) 扩展；
  • 区间 \([l,r]\rightarrow x\) 的贡献可以差分为 \([1,r]\rightarrow x\) 减去 \([1,l-1]\rightarrow x\)（统计数对数量的题目通常都满足这个条件）；
  • 离线后，通过平衡可以将单次查询时间复杂度降低到 \(O(1)\)，同时单次修改时间复杂度不能超过 \(O(\sqrt n)\)；

例题

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

题意

给定一个长度为 \(n\) 的序列。有 \(m\) 次询问，每次询问查询一个区间 \([l,r]\) 的逆序对数量。

\(n,m\le 10^5\)

考虑莫队，如何处理扩展和删除操作。我们希望 \(O(1)\) 查询一个区间 \([l,r]\) 中 \(\le x\) 或 \(\ge x\) 的数有多少个，一共有 \(n\sqrt m\) 组询问。如果我们在莫队时维护数据结构，并在线查询，则时间复杂度不会低于 \(O(n\sqrt m\log n)\)。考虑离线后使用二维偏序解决。

显然二维偏序普通做法的时间复杂度将达到 \(O(n\log n+n\sqrt m\log n)\)。由于二次离线的查询次数 \(n\sqrt m\) 和序列长度 \(n\) 不同阶，考虑使用 \(O(\sqrt n)-O(1)\) 的分块代替树状数组，时间复杂度有最小值 \(O(n\sqrt n + n\sqrt m)\)，可以通过本题。

注意：莫队二次离线求出的答案实际上是两次查询答案的差。因此最后需要做前缀和。

但是本题要求线性空间。考虑将本质相似的一系列查询归为一个查询。记区间 \([l,r]\) 中 \(\le a_i\) 的数字数量为 \(w\big([l,r],i\big)\)。以向右扩展为例，假设当前区间右端点为 \(r\)，目标区间右端点为 \(r_0\)。本轮扩展产生的贡献可记为

\[ \sum_{i=r+1}^{r_0}{w\Big([l,i-1],i\Big)} \]

差分：

\[ \begin{align*} &\sum_{i=r+1}^{r_0}{w\Big([l,i-1],i\Big)}\\ =&\sum_{i=r+1}^{r_0}{w\Big([1,i-1],i\Big)}-\sum_{i=r+1}^{r_0}{w\Big([1,l-1],i\Big)} \end{align*} \]

\(w\big([1,i-1],i\big)\) 可以 \(O(n\log n)\) 预处理，查询时即可 \(O(1)\) 求出。\(\sum_{i=r+1}^{r_0}{w\Big([1,l-1],i\Big)}\) 的贡献可以通过三元组 \((l-1,r+1,r_0)\) 表示；数点时暴力枚举 \(i\in [r+1,r_0]\)，并 \(O(1)\) 求出答案贡献到 ans 数组即可。由于扩展的总次数不超过 \(m\)，因此空间为线性。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const int N = 1e5 + 10;

struct fast_istream {
    char ch;
    template<typename _Tp>
    inline fast_istream& operator>>(_Tp &x) {
        while(!isdigit(ch = getchar_unlocked()));
        x = ch - 48;
        while(isdigit(ch = getchar_unlocked())) x = x * 10 + ch - 48;
        return *this;
    }
} fin;

struct fast_ostream {
    int buf[60], nb;
    inline fast_ostream& operator<<(char c) {
        putchar(c);
        return *this;
    }
    template<typename _Tp>
    inline fast_ostream& operator<<(_Tp x) {
        do buf[++nb] = x % 10, x /= 10; while(x);
        while(nb) putchar(buf[nb--] + 48);
        return *this;
    }
} fout;

int blen, blo[N];
struct Query {
    int l, r, id;
    inline bool operator<(const Query& other) const {
        if(blo[l] != blo[other.l]) return blo[l] < blo[other.l];
        return (blo[l] & 1) ? (r < other.r) : (r > other.r);
    }
} q[N];

template<class _Comp>
struct Op {
    int tp, key, l, r, w, id;
    _Comp cmp;
    inline bool operator<(const Op& other) const {
        if(key != other.key) return cmp(key, other.key);
        return tp > other.tp;
    }
};

int n, m, nn;
int a[N];

void lisanhua() {
    int num[N];
    for(int i = 1; i <= n; i++) num[++nn] = a[i];
    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);
    for(int i = 1; i <= n; i++) a[i] = lower_bound(num + 1, num + 1 + nn, a[i]) - num;
}

namespace BIT {
    ll sum[N];
    inline int lowbit(int x) { return x & -x; }
    inline void add(int p, ll v) {
        for(int i = p; i <= nn; i += lowbit(i)) sum[i] += v;
    }
    inline ll query(int p) {
        ll res = 0;
        for(int i = p; i > 0; i -= lowbit(i)) res += sum[i];
        return res;
    }
    inline void clear() {
        for(int i = 1; i <= nn; i++) sum[i] = 0;
    }
}

ll f1[N], f2[N];
void get_pref_ans() {
    for(int i = 1; i <= n; i++) {
        f1[i] = BIT::query(nn - a[i]);
        BIT::add(nn - a[i] + 1, 1);
    }
    BIT::clear();
    for(int i = n; i >= 1; i--) {
        f2[i] = BIT::query(a[i] - 1);
        BIT::add(a[i], 1);
    }
    for(int i = 1; i <= n; i++) f1[i] += f1[i - 1];
    for(int i = n; i >= 1; i--) f2[i] += f2[i + 1];
}

// O(1) sum
namespace bloA {
    ll a[N], tag[N];
    int n, blen;
    inline int blo(int x) { return (x + blen - 1) / blen; }
    inline int ed(int x) { return min(n, blo(x) * blen); }
    inline void init(int _n, int _blen) {
        n = _n;
        blen = _blen;
    }
    inline void clear() {
        for(int i = 1; i <= n; i++) a[i] = 0;
        for(int i = 1; i <= blo(n); i++) tag[i] = 0;
    }
    inline void add(int p) {
        int tmp = ed(p);
        while(p <= tmp) ++a[p++];
        if(p > n) return;
        tmp = blo(n);
        for(int i = blo(p); i <= tmp; i++) {
            ++tag[i];
        }
    }
    inline ll query(int p) {
        if(!p) return 0;
        return a[p] + tag[blo(p)];
    }
    inline ll sum(int l, int r) {
        if(l > r) return 0;
        return query(r) - query(l - 1);
    }
}

ll ans[N];
int c_l, c_r;

vector<Op<less<int>   >> op1;
vector<Op<greater<int>>> op2;

void calc1() {
    sort(op1.begin(), op1.end());
    for(auto &o : op1) {
        if(o.tp == 1) {
            bloA::add(o.w);
        } else {
            for(int i = o.l; i <= o.r; i++) {
                ans[o.id] += o.w * bloA::sum(a[i] + 1, nn);
            }
        }
    }
}

void calc2() {
    sort(op2.begin(), op2.end());
    bloA::clear();
    for(auto &o : op2) {
        if(o.tp == 1) {
            bloA::add(o.w);
        } else {
            for(int i = o.l; i <= o.r; i++) {
                ans[o.id] += o.w * bloA::sum(1, a[i] - 1);
            }
        }
    }
}

signed main() {

    fin >> n >> m;
    for(int i = 1; i <= n; i++) fin >> a[i];
    for(int i = 1; i <= m; i++) fin >> q[i].l >> q[i].r;
    for(int i = 1; i <= m; i++) q[i].id = i;

    lisanhua();

    get_pref_ans();

    blen = max(1, (int)(n / sqrt(m)));
    for(int i = 1; i <= n; i++) blo[i] = (i + blen - 1) / blen;

    sort(q + 1, q + 1 + m);

    op1.reserve(n);
    op2.reserve(n);

    c_l = 1, c_r = 0;
    for(int i = 1; i <= m; i++) {
        int l = q[i].l, r = q[i].r, id = q[i].id;
        if(c_r < r) {
            ans[id] += f1[r] - f1[c_r];
            op1.push_back({0, c_l - 1, c_r + 1, r, -1, id});
            c_r = r;
        }
        if(l < c_l) {
            ans[id] += f2[l] - f2[c_l];
            op2.push_back({0, c_r + 1, l, c_l - 1, -1, id});
            c_l = l;
        }
        if(r < c_r) {
            ans[id] -= f1[c_r] - f1[r];
            op1.push_back({0, c_l - 1, r + 1, c_r, 1, id});
            c_r = r;
        }
        if(c_l < l) {
            ans[id] -= f2[c_l] - f2[l];
            op2.push_back({0, c_r + 1, c_l, l - 1, 1, id});
            c_l = l;
        }
    }

    for(int i = 1; i <= n; i++) op1.push_back({1, i, 0, 0, a[i], 0});
    for(int i = 1; i <= n; i++) op2.push_back({1, i, 0, 0, a[i], 0});

    bloA::init(nn, max(1, (int)sqrt(nn)));
    calc1();
    calc2();

    for(int i = 1; i <= m; i++) ans[q[i].id] += ans[q[i - 1].id];

    for(int i = 1; i <= m; i++) {
        fout << ans[i] << '\n';
    }

    return 0;
}

P4887 【模板】莫队二次离线（第十四分块(前体)）

题意

给定一个长为 \(n\) 的序列 \(a\) 和常数 \(k\)。有 \(m\) 次询问，每次询问给定一个区间 \([l,r]\)，询问区间中有多少对数满足 \(\operatorname{popcnt}(a_i\oplus a_j)=k\)。

\(n,m\le 10^5,\ a_i\le 2^{14}=16384\)。

\(\max_{i\in [0,14]}\left\{\binom{14}{i}\right\}=\binom{14}{7}=3432\)

考虑莫队。如果不进行二次离线，那么添加单个元素并统计贡献的最优时间复杂度不低于 \(O\left(n\sqrt m\binom{14}{7}\right)\)。

仔细分析我们要解决的子问题：求出 \(i\in[l,r]\) 的有多少个元素 \(\operatorname{popcnt}(a_i\oplus x)=k\)。这显然可差分。

现在问题转化为求前缀 \([1,p]\) 中有多少个元素满足上面的条件。\(O(1)-O(\binom{14}{7})\) 显然容易，只需要用一个桶数组记录即可。我们希望提高修改的时间复杂度，降低查询的时间复杂度。每次插入数字 \(x\) 时，我们可以遍历所有 \(\operatorname{popcnt}(y)=k\) 的 \(y\)，然后贡献到 \(f[x\oplus y]\) 位置。查询时 \(O(1)\) 单点查询 \(f[x]\) 即可。

时间复杂度为 \(O(n\sqrt m+n\binom{14}{7})\)。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
const int K = 14;

int blen, blo[N];
struct Query {
    int l, r, id;
    inline bool operator<(const Query& other) const {
        if(blo[l] != blo[other.l]) return blo[l] < blo[other.l];
        if(blo[l] & 1) return r < other.r;
        return r > other.r;
    }
} q[N];

struct Op {
    int tp, key, l, r, w, id;
    inline bool operator<(const Op& other) const {
        if(key != other.key) return key < other.key;
        return tp > other.tp;
    }
};

int vld[N], nv; // k 位 1 的二进制数

int n, m, k;
int a[N];
ll t[N], f[N];   // i 对 [1, i - 1] 的贡献
ll ans[N]; // 每个询问的答案

vector<Op> op;

void get_vld() {
    int cnt[N] = {0};
    for(int i = 1; i < (1 << K); i++) cnt[i] = cnt[i ^ (i & -i)] + 1;
    for(int i = 0; i < (1 << K); i++) {
        if(cnt[i] == k) {
            vld[++nv] = i;
        }
    }
}

void get_pref_ans() {
    for(int i = 1; i <= n; i++) {
        f[i] = t[a[i]];
        for(int j = 1; j <= nv; j++) {
            ++t[a[i] ^ vld[j]];
        }
    }
    for(int i = 1; i <= n; i++) {
        f[i] += f[i - 1];
    }
    for(int i = 0; i <= 16384; i++) {
        t[i] = 0;
    }
}

int c_l, c_r, c_ans;

int main() {

    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> q[i].l >> q[i].r;
    for(int i = 1; i <= m; i++) q[i].id = i;

    blen = max(1, (int)(n / sqrt(m)));
    for(int i = 1; i <= n; i++) blo[i] = (i + blen - 1) / blen;

    get_vld();
    get_pref_ans();

    sort(q + 1, q + 1 + m);

    c_l = 1, c_r = 0;
    for(int i = 1; i <= m; i++) {
        int l = q[i].l, r = q[i].r, id = q[i].id;
        if(c_r < r) {
            ans[id] += f[r] - f[c_r];
            op.push_back({0, c_l - 1, c_r + 1, r, -1, id});
            c_r = r;
        }
        if(c_l > l) {
            ans[id] -= f[c_l - 1] - f[l - 1] + ((k == 0) ? (c_l - l) : 0);
            op.push_back({0, c_r, l, c_l - 1, 1, id});
            c_l = l;
        }
        if(c_r > r) {
            ans[id] -= f[c_r] - f[r];
            op.push_back({0, c_l - 1, r + 1, c_r, 1, id});
            c_r = r;
        }
        if(c_l < l) {
            ans[id] += f[l - 1] - f[c_l - 1] + ((k == 0) ? (l - c_l) : 0);
            op.push_back({0, c_r, c_l, l - 1, -1, id});
            c_l = l;
        }
    }

    for(int i = 1; i <= n; i++) {
        op.push_back({1, i, 0, 0, a[i], 0});
    }

    sort(op.begin(), op.end());

    for(Op &o : op) {
        if(o.tp == 1) {
            for(int i = 1; i <= nv; i++) {
                ++t[o.w ^ vld[i]];
            }
        } else {
            for(int i = o.l; i <= o.r; i++) {
                ans[o.id] += o.w * t[a[i]];
            }
        }
    }

    for(int i = 2; i <= m; i++) {
        ans[q[i].id] += ans[q[i - 1].id];
    }

    for(int i = 1; i <= m; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}