莫队二次离线学习笔记

在进行莫队时，若不能快速地在线计算移动区间后的贡献变化，可以考虑将 $O(n\sqrt{n})$ 个移动再次离线，每次 $O(1)$ 求出贡献变化。

这就是所谓莫队二次离线。

注意这里贡献要求具有可减性，因为我们每次求的是贡献变化。

思路

目前，运用该 trick 的题目通常为求区间中合法点对数量。

设 $S([l_1, r_1], [l_2, r_2])$ 为前面的数在 $[l_1, r_1]$ 位置，后面的数在 $[l_2, r_2]$ 位置所组成的合法点对数。

考虑从上一个区间 $[l_1, r_1]$ 转移至当前需求区间 $[l_2, r_2]$ 的过程。不失一般性地，设 $l_1 < l_2, r_1 < r_2$（其他情况可类似推出）。

$$\begin{aligned}
&\ S([l, r], [l, r])\\
&= S([1, r], [1, r]) + S([l, n], [l, n])\\
&+ S([1, l - 1], [r + 1, n]) - S([1, n], [1, n])
\end{aligned}$$

注意到：

$$\begin{aligned}
&\ S([1, l_2 - 1], [r_2 + 1, n]) - S([1, l_1 - 1], [r_1 + 1, n])\\
&= S([l_1, l_2 - 1], [r_2 + 1, n]) - S([1, l_1 - 1], [r_1 + 1, r_2])
\end{aligned}$$

所以：

$$\begin{aligned}
&\ S([l_2, r_2], [l_2, r_2]) - S([l_1, r_1], [l_1, r_1])\\
&= S([1, r_2], [1, r_2]) - S([1, r_1], [1, r_1]) - S([l_1, n], [l_1, n]) + S([l_2, n], [l_2, n]) \\
&- S([1, l_1 - 1], [r_1 + 1, r_2]) + S([l_1, l_2 - 1], [r_2 + 1, n])
\end{aligned}$$

虽然基本每个题都是这个式子，但因为太长实在没有记的必要，直接画出1,n,l_1,r_1,l_2,r_2现推往往更快。

下面是原来的较为繁琐的推法：

$$\begin{aligned}
&\ S([l_2, r_2], [l_2, r_2]) - S([l_1, r_1], [l_1, r_1])\\
&= S([l_2, r_2], [r_1 + 1, r_2]) - S([l_1, l_2 - 1], [l_1, r_1])\\
&= (S([1, r_2], [r_1 + 1, r_2]) - S([1, l_1 - 1], [r_1 + 1, r_2]))\\
&- (S([l_1, l_2 - 1], [l_1, n]) - S([l_1, l_2 - 1], [r_2 + 1, n]))\\
&= S([1, r_2], [1, r_2]) - S([1, r_1], [1, r_1]) - S([l_1, n], [l_1, n]) + S([l_2, n], [l_2, n]) \\
&- S([1, l_1 - 1], [r_1 + 1, r_2]) + S([l_1, l_2 - 1], [r_2 + 1, n])
\end{aligned}$$

故，不失一般性地，只需考虑 $S([1, r], [1, r]), S([1, l_1 - 1], [r_1 + 1, r_2])$ 的求法。前者一般因题而异且不为难点，故本处只考虑后者。

不妨为每个位置开一个vector。将一个 $S([1, l_1 - 1], [r_1 + 1, r_2])$ 的询问记录在第 $l_1 - 1$ 个vector上。

然后使用可以用类似扫描线的做法，依次处理每个vector上的询问，

例题

「Ynoi2019模拟赛」Yuno loves sqrt technology II

Luogu 5047

给定长 $O(n)$ 序列，离线 $O(n)$ 次查询区间逆序对，希望做到 $O(n\sqrt{n})$ 复杂度。

主要思路

显然利用树状数组有复杂度 $O(n\sqrt{n}\log n)$ 的莫队，且瓶颈在于计算移动区间后的贡献变化。

$S([1, r], [1, r])$ 可以直接使用树状数组求出。考虑 $S([1, l_1 - 1], [r_1 + 1, r_2])$。

套上上面那套东西，则问题转化为维护可重集，要求 $O(n\sqrt{n})$ 次查询比某数小的元素个数且有 $O(n)$ 次加点。

利用一个值域分块即可做到 $O(\sqrt{n})$ 加点，$O(1)$ 查询。

故总时间复杂度 $O(n\sqrt{n})$，空间 $O(n)$。

#include <bits/stdc++.h>
namespace my_std {
using namespace std;
#define reg register
#define Rint register int
#define FOR(i, a, b) for (register int i = (a), ed_##i = (b); i <= ed_##i; ++i)
#define ROF(i, a, b) for (register int i = (a), ed_##i = (b); i >= ed_##i; --i)
#define Templ(T) template <typename T>
typedef long long i64;

#define MMR (1 << 23)
static char InB[MMR], *In_s = InB;
static char OutB[MMR], *Out_s = OutB;
inline void F_In(){ fread(InB, 1, MMR, stdin); }
inline void F_Out(){ fwrite(OutB, 1, Out_s - OutB, stdout); }
inline int read(){
    Rint res = 0;
    for(; *In_s < 48; ++In_s);
    for(; *In_s > 47;) res = res * 10 + (*In_s++ & 15);
    return res;
}
inline void write(reg i64 x){
    static char tmp[20], *t = tmp;
    do{
        *++t = (x % 10) ^ 48, x /= 10;
    }while(x);
    while(t != tmp) *Out_s++ = *t--;
    *Out_s++ = 10;
}

Templ(_Tp) inline int chkmin(_Tp &x, _Tp y) { return x > y ? x = y, 1 : 0; }
Templ(_Tp) inline int chkmax(_Tp &x, _Tp y) { return x < y ? x = y, 1 : 0; }
} // namespace my_std
using namespace my_std;

#define N 100010
#define BN 330
#define M 317
#define PB push_back
int n, m;
int a[N], bl[N], Lb[BN], Rb[BN];
i64 ans[N];
i64 sumL[N], sumR[N];//前/后 i 个有多少逆序对
int Sb[BN], Cb[N];//块前/后缀和，点在块内前/后缀和

struct BiT{
    int a[N];
    inline void upd(int x){
        for(; x <= n; x += x & (-x)) ++a[x];
    }
    inline int qry(int x){
        Rint res = 0;
        for(; x; x ^= x & (-x)) res += a[x];
        return res;
    }
}T;

struct Q{
    int l, r, id;
    inline bool operator <(const Q &rhs)const{
        return bl[l] == bl[rhs.l] ? 
            ((bl[l] & 1) ? r > rhs.r : r < rhs.r) : 
            l < rhs.l;
    }
}q[N];
struct Node{
    int l, r, i, v;
};
vector<Node> vL[N], vR[N];

void init(){
    n = read(), m = read();
    int *aa = new int[N];
    FOR(i, 1, n) aa[i] = a[i] = read();
    sort(aa + 1, aa + n + 1);
    FOR(i, 1, n) a[i] = lower_bound(aa + 1, aa + n + 1, a[i]) - aa;
    delete aa;

    Rint c = M;
    FOR(i, 1, n){
        bl[i] = bl[i - 1], ++c;
        if(c > M) Rb[bl[i]] = i - 1, Lb[++bl[i]] = i, c = 1;
    }
    Rb[bl[n]] = n;

    FOR(i, 1, m) q[i].l = read(), q[i].r = read(), q[i].id = i;
    sort(q + 1, q + m + 1);
    q->l = 1;

    FOR(i, 1, n) sumL[i] = sumL[i - 1] + i - 1 - T.qry(a[i]), T.upd(a[i]);
    memset(T.a, 0, sizeof(T.a));
    ROF(i, n, 1) sumR[i] = sumR[i + 1] + T.qry(a[i] - 1), T.upd(a[i]);
}

int main() {
    F_In();
    init();
    FOR(i, 1, m){
        ans[i] = sumL[q[i].r] - sumL[q[i - 1].r] + sumR[q[i].l] - sumR[q[i - 1].l];
        if(q[i].r > q[i - 1].r){
            vR[q[i - 1].l - 1].PB((Node){q[i - 1].r + 1, q[i].r, i, -1});
        }
        else if(q[i].r < q[i - 1].r){
            vR[q[i - 1].l - 1].PB((Node){q[i].r + 1, q[i - 1].r, i, 1});
        }
        if(q[i].l < q[i - 1].l){
            vL[q[i].r + 1].PB((Node){q[i].l, q[i - 1].l - 1, i, -1});
        }
        else if(q[i].l > q[i - 1].l){
            vL[q[i].r + 1].PB((Node){q[i - 1].l, q[i].l - 1, i, 1});
        }
    }//二次离线
    FOR(i, 1, n){
        reg const int p = bl[a[i]];
        FOR(v, 1, p - 1) ++Sb[v];
        FOR(v, Lb[p], a[i]) ++Cb[v];
        for(reg Node &x: vR[i]){
            reg i64 res = 0;
            FOR(j, x.l, x.r) res += Sb[bl[a[j] + 1]] + Cb[a[j] + 1];
            x.v > 0 ? (ans[x.i] += res) : (ans[x.i] -= res);
        }
    }
    memset(Cb, 0, sizeof(Cb)), memset(Sb, 0, sizeof(Sb));
    ROF(i, n, 1){
        reg const int p = bl[a[i]];
        ROF(v, M, p + 1) ++Sb[v];
        ROF(v, Rb[p], a[i]) ++Cb[v];
        for(reg Node &x: vL[i]){
            reg i64 res = 0;
            FOR(j, x.l, x.r) res += Sb[bl[a[j] - 1]] + Cb[a[j] - 1];
            x.v > 0 ? (ans[x.i] += res) : (ans[x.i] -= res);
        }
    }
    reg i64 *res = new i64[N];
    FOR(i, 1, m) res[q[i].id] = ans[i] += ans[i - 1];
    FOR(i, 1, m) write(res[i]);
    delete res;
    F_Out();
    return 0;
}