跳到主要内容

学习笔记：莫队二次离线

前置知识​

  1. 莫队

引入​

莫队作为一个极为优雅的暴力算法，具有相当优秀的时间复杂度，在面对区间能够 O(1)O(1) 进行单点扩张或收缩的情况时，往往能够得到不低的分数，然而当单点扩张或收缩的复杂度为 kk 时，莫队的时间复杂度就是 O(nnk)O(n\sqrt{n}k)，有可能 TLE

这时候我们就可以引入莫队二次离线，将算法的时间复杂度进一步优化到 O(nn+nk)O(n\sqrt{n}+nk)，进而通过该类题目

思路​

在进行区间扩展或收缩时，假如我们需要处理的信息可以差分，则可以考虑二次离线

例：

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

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

直接转移的话单次转移复杂度很显然是 O(log⁡n)O(\log n)，但转移过程所需要的信息是「一个数在某个区间内的排名」，注意到它可以关于区间差分，所以我们使用二次离线优化

以 [l,r][l,r] 到 [l,r+1][l,r+1] 为例，此时我们需要求的是在 [l,r][l,r] 区间内有多少比 ar+1a_{r+1} 大的数

设 f(x,r)f(x,r) 表示 [1,r][1,r] 区间内比 axa_x 大的数，g(x,r)g(x,r) 表示 [1,r][1,r] 区间内比 axa_x 小的数

则此时答案的变化量可表示为 f(r+1,r)−f(r+1,l−1)f(r+1,r)-f(r+1,l-1)

同理 [l,r][l,r] 收缩到 [l,r−1][l,r-1] 的变化量可表示为 f(r,l−1)−f(r,r−1)f(r,l-1)-f(r,r-1)；从 [l,r][l,r] 扩张到 [l−1,r][l-1,r] 的变化量可表示为 g(l−1,r)−g(l−1,l−2)g(l-1,r)-g(l-1,l-2)； [l,r][l,r] 收缩到 [l+1,r][l+1,r] 的变化量可表示为 g(l,l−1)−f(l,r)g(l,l-1)-f(l,r)

对于 f(x,x−1)f(x,x-1) 和 g(x,x−1)g(x,x-1) 我们可以使用树状数组进行预处理

而对于其余的项，我们将 xx 存储下来离线处理

而对于离线的部分，问题就转化为向一个集合中加入数，查询一个数在集合中的排名，我们考虑使用值域分块在 O(nn)O(n\sqrt{n}) 内解决这个问题，因而总复杂度为 O(nm+nn)O(n\sqrt{m}+n\sqrt{n})

最后使用前缀和就可以得到正确答案。

代码示例​

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

const ll N = 100005;
ll n , m , k , a[N] , bl[N];
vector <tuple<ll , ll , ll>> v[N];

struct query
{
    ll l , r , id;
    ll ans;
};
query q[N];

signed main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> k;
    if(k > 14) {for(ll i = 1 ; i <= m ; i++) cout << 0 << '\n'; return 0;}
    for(ll i = 1 ; i <= n ; i++) cin >> a[i];
    for(ll i = 1 ; i <= m ; i++) cin >> q[i].l >> q[i].r , q[i].id = i;
    vector <ll> buc;
    for(ll i = 0 ; i < 16384 ; i++) if(__builtin_popcount(i) == k) buc.push_back(i);
    ll T = sqrt(n);
    for(ll i = 1 ; i <= n ; i++) bl[i] = (i - 1) / T + 1;
    sort(q + 1 , q + m + 1 , [](query a , query b) {return bl[a.l] == bl[b.l] ? a.r < b.r : a.l < b.l;});
    ll t[N] , pref[N];
    for(ll i = 1 ; i <= n ; i++)
    {
        for(auto x : buc) t[a[i] ^ x]++;
        pref[i] = t[a[i + 1]];
    }
    memset(t , 0 , sizeof t);
    for(ll i = 1 , L = 1 , R = 0 ; i <= m ; i++)
    {
        ll l = q[i].l , r = q[i].r;
        if(L < l) v[R].emplace_back(L , l - 1 , -i);
        while(L < l) {q[i].ans += pref[L - 1]; L++;} 
        if(L > l) v[R].emplace_back(l , L - 1 , i);
        while(L > l) {q[i].ans -= pref[L - 2]; --L;}
        if(R < r) v[L - 1].emplace_back(R + 1 , r , -i);
        while(R < r) {q[i].ans += pref[R]; ++R;}
        if(R > r) v[L - 1].emplace_back(r + 1 , R , i);
        while(R > r) {q[i].ans -= pref[R - 1]; --R;}
    }
    ll ans[N];
    for(ll i = 1 , id , l , r ; i <= n ; i++)
    {
        for(auto x : buc) t[a[i] ^ x]++;
        for(const auto& x : v[i])
        {
            tie(l , r , id) = x;
            for(ll j = l , tmp = 0 ; j <= r ; j++)
            {
                tmp = t[a[j]];
                if(j <= i && k == 0) tmp--;
                if(id < 0) q[-id].ans -= tmp;
                else q[id].ans += tmp;
            }
        }
    }
    for(ll i = 1 ; i <= m ; i++) q[i].ans += q[i - 1].ans;
    for(ll i = 1 ; i <= m ; i++) ans[q[i].id] = q[i].ans;
    for(ll i = 1 ; i <= m ; i++) cout << ans[i] << '\n';
    return 0;
}