二次离线莫队

问题

对于一些离线问题，往往需要用莫队解决。

但是在使用莫队的过程中，我们往往需要使用在线数据结构维护信息。但是一些复杂的信息往往需要带有 $O(\log n)$复杂度的数据结构才能维护，这使得整个算法的复杂度升高到了 $O(n^{1.5}\log n)$。

比如下面的问题：

• 离线询问一个序列的区间逆序对数

在使用莫队算法解决这一问题的时候，我们不得不用树状数组维护区间逆序对个数，非常慢。

有没有办法避免这一情况呢？

分析

以区间逆序对为例，我们需要 $O(n^{1.5})$次对某一数据结构实施动态的修改和查询操作。

是否可以将这些动态的操作离线下来，降低复杂度呢？

解决

在莫队算法的运行过程中，假设上一个处理的区间为 $[l,r]$，当前需要处理的区间为 $[l,r’]$，也就是说我们需要将区间的右端点向右移动多次。这时，我们需要依次求出区间 $([l,r+i],[r+i+1,r+i+1])$组成的逆序对。将这些区间差分之后，我们实际上需要求出区间 $([1,l-1],[r+1,r’])$组成的逆序对和区间 $([1,r+i],[r+i+1,r+i+1])$组成的逆序对。

观察这两个差分后的区间对，我们发现，这两种分别满足以下性质：

• 一个前缀 $P$和不相邻的一个区间 $I$组成的，总数为 $O(n)$，且 $I$的长度总和不超过 $O(n\sqrt{n})$
• 一个前缀 $P$和这个前缀后面紧跟的一个元素组成的，总数为 $O(n\sqrt{n})$，且本质不同的这样的区间对只有 $O(n)$个

对于第一种区间对，我们可以利用某种可以 $O(\sqrt{n})$修改，$O(1)$询问的数据结构，获得答案。由于总数不多，我们将这些区间用链表或者可变长数组保存在对应位置，从前往后扫描时依次询问即可。

对于第二种区间对，由于本质不同的这样的区间很少，并且每次询问的都是连续的一段前缀 $P_l\dots P_r$所对应的答案，我们不妨按照第一种区间对的处理方式获得所有本质不同的区间对的答案，并且做一次前缀和，询问时只需要 $O(1)$访问。

上述算法的瓶颈在于第一种区间对的处理，其总时间复杂度为 $O(n^{1.5})$

对于右端点减，左端点加，左端点减等操作，我们亦可如法炮制。

应用

利用二次离线莫队求区间逆序对。luoguP5047:

// luogu-judger-enable-o2
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#define MX 102005
#define MB 318

using namespace std;

typedef long long ll;

template <typename T> void read(T& x)
{
    x = 0; char c = getchar(); bool f = 0;
    while(!isdigit(c) && c!='-') c = getchar();
    if(c == '-') f = 1, c = getchar();
    while(isdigit(c)) x = x*10+c-'0', c = getchar();
    if(f) x = -x;
}

int lft[MB+2], rgt[MB+2], bel[MX+2];

void init()
{
    for(int i=1; i<=MB; i++) lft[i] = i*MB-MB+1, rgt[i] = i*MB;
    for(int i=1; i<=MB; i++)
        for(int j=lft[i]; j<=rgt[i]; j++)
            bel[j] = i;
}

struct BLOCK
{
    int blk[MB+2], val[MX+2];

    void add(int p, int x)
    {
        for(int i=MB; i>=1; i--)
            if(lft[i] >= p) blk[i] += x;
            else
            {
                for(int j=p; j<=rgt[i]; j++) val[j] += x;
                break;
            }
    }

    int qur(int p)
    {
        return blk[bel[p]] + val[p];
    }
} B;

struct NODE
{
    int l, r, id;

    bool operator < (const NODE &t) const {return (bel[l]!=bel[t.l]) ? (bel[l]<bel[t.l]) : ((bel[l]&1) ? (r<t.r) : (r>t.r));}
};

struct ITV
{
    int l, r;

    ITV (const int &l0 = 0, const int &r0 = 0) : l(l0), r(r0) {}
};

struct MOQ
{
    int n, m;
    NODE qur[MX];

    vector<ITV> preq[MX], sufq[MX];
    vector<ll> prea[MX], sufa[MX];
    int prec[MX], sufc[MX];
    ll pren[MX], sufn[MX];
    ll ans[MX];

    void init(int n0, int m0, int *seq)
    {
        n = n0, m = m0;
        sort(qur+1, qur+m+1);
        int cl = 2, cr = 1;
        for(int i=1; i<=m; i++)
        {
            if(qur[i].r > cr) preq[cl-1].push_back(ITV(cr+1, qur[i].r)), cr = qur[i].r;
            if(qur[i].l < cl) sufq[cr+1].push_back(ITV(qur[i].l, cl-1)), cl = qur[i].l;
            if(qur[i].r < cr) preq[cl-1].push_back(ITV(qur[i].r+1, cr)), cr = qur[i].r;
            if(qur[i].l > cl) sufq[cr+1].push_back(ITV(cl, qur[i].l-1)), cl = qur[i].l;
        }
        for(int i=0; i<n; i++)
        {
            if(i) B.add(seq[i], +1);
            for(auto j : preq[i])
            {
                ll now = 0;
                for(int x=j.l; x<=j.r; x++) now += i-B.qur(seq[x]);
                prea[i].push_back(now);
            }
            pren[i] = i-B.qur(seq[i+1]);
        }
        for(int i=1; i<=n; i++) pren[i] += pren[i-1];
        memset(B.val, 0, sizeof(B.val));
        memset(B.blk, 0, sizeof(B.blk));
        for(int i=n+1; i>=1; i--)
        {
            if(i <= n) B.add(seq[i], +1);
            for(auto j : sufq[i])
            {
                ll now = 0;
                for(int x=j.l; x<=j.r; x++) now += B.qur(seq[x]-1);
                sufa[i].push_back(now);
            }
            if(i > 1) sufn[i] = B.qur(seq[i-1]-1);
        }
        for(int i=n; i>=1; i--) sufn[i] += sufn[i+1];
        ll cur_ans = 0; cl = 2, cr = 1;
        for(int i=1; i<=m; i++)
        {
            if(qur[i].r > cr) cur_ans += pren[qur[i].r-1] - pren[cr-1] - prea[cl-1][prec[cl-1]++], cr = qur[i].r;
            if(qur[i].l < cl) cur_ans += sufn[qur[i].l+1] - sufn[cl+1] - sufa[cr+1][sufc[cr+1]++], cl = qur[i].l;
            if(qur[i].r < cr) cur_ans -= pren[cr-1] - pren[qur[i].r-1] - prea[cl-1][prec[cl-1]++], cr = qur[i].r;
            if(qur[i].l > cl) cur_ans -= sufn[cl+1] - sufn[qur[i].l+1] - sufa[cr+1][sufc[cr+1]++], cl = qur[i].l;
            ans[qur[i].id] = cur_ans;
        }
    }
} M;

int n, m;
int seq[MX];

void discrete()
{
    static int rel[MX], rnum;
    memmove(rel, seq, sizeof(rel));
    sort(rel+1, rel+n+1);
    rnum = unique(rel+1, rel+n+1) - rel - 1;
    for(int i=1; i<=n; i++) seq[i] = lower_bound(rel+1, rel+rnum+1, seq[i]) - rel;
}

int main()
{
    read(n); read(m);
    for(int i=1; i<=n; i++) read(seq[i]);
    for(int i=1; i<=m; i++) read(M.qur[i].l), read(M.qur[i].r), M.qur[i].id = i;
    discrete();
    init();
    M.init(n, m, seq);
    for(int i=1; i<=m; i++) printf("%lld\n", M.ans[i]);
    return 0;
}