离线算法学习笔记

tallnut · 2025-06-17 18:31:00 · 算法·理论

离线思想基础

离线思想是指将整道题的所有询问全部输入好存储下来，并对其进行一定的操作（通常为按某种顺序排序）后，更高效地回答查询。但只能解决不强制在线的题目。这不是废话么

下面用一道最经典的例题引入离线思想。

P1972

给定数列，不带修，多次查询区间内有几种不同的数。

其实我们只需要保留每种数字各一个即可，比较容易实现的方式是选取最右边的。对于每种数，只关心它最后一次出现的位置。这样就把原序列转换成了一个 01 序列，表示该数是不是最后一次出现。

如果询问能保证右端点单调递增，就只需要用树状数组在新的 01 序列上进行区间查询即可。于是使用离线思想，询问存储下来后对右端点排序，同时提前记录每个询问的 id 方便按原顺序输出。

代码：

#include <bits/stdc++.h>
//#define MULTITEST
using namespace std;
typedef long long ll;
#define int ll
#define rep1(i,x,y) for (int i = (x);i <= (y);i++)
#define rep2(i,x,y) for (int i = (x);i >= (y);i--)
#define rep3(i,x,y,z) for (int i = (x);i <= (y);i += (z))
#define rep4(i,x,y,z) for (int i = (x);i >= (y);i -= (z))
#define cl(a) memset(a,0,sizeof(a))
const int N = 1e6 + 10;
int n,q;
int a[N],ans[N],lst[N],id[N];
struct xxx
{
    int l;
    int r;
    int id;
    bool operator<(const xxx& xx) { return r < xx.r; }
} b[N];
class fenwick
{
    int a[N];
    inline int lowbit(int x) { return x & (-x); }
    int sum(int x)
    {
        int ans = 0;
        rep4(i,x,1,lowbit(i))
            ans += a[i];
        return ans;
    }
    public:
        fenwick() { cl(a); }
        void modify(int k,int x)
        {
            rep3(i,k,N - 1,lowbit(i))
                a[i] += x;
        }
        int query(int l,int r) { return sum(r) - sum(l - 1); }
} t;
void solve()
{
    cin >> n;
    rep1(i,1,n)
        cin >> a[i];
  cin >> q;
    rep1(i,1,q)
    {
        cin >> b[i].l >> b[i].r;
        b[i].id = i;
    }
    sort(b + 1,b + q + 1);
    rep1(i,1,n)
    {
        lst[i] = id[a[i]];
        id[a[i]] = i;
    }
    int j = 1;
    rep1(i,1,n)
    {
        t.modify(i,1);
        if (lst[i])
            t.modify(lst[i],-1);
        for (;j <= q && b[j].r == i;j++)
            ans[b[j].id] = t.query(b[j].l,b[j].r);
    }
    rep1(i,1,q)
        cout << ans[i] << '\n';
}
signed main()
{
    int t;
#ifdef MULTITEST
    cin >> t;
#else
    t = 1;
#endif
    while (t--)
        solve();
}

CDQ 分治

CDQ 分治是一类特殊的分治，核心思想为：计算一个子问题对另一个子问题的贡献。

先按照正常的分治三部曲，递归处理左右子问题，再将左半部分视为修改，右半部分视为查询，用数据结构维护。

例题

首先是 CDQ 分治的最经典应用：n 维偏序问题。

二维偏序

有 n 个物品，每个两种属性 a_i,b_i，求最长不下降子序列。

可以直接用树状数组之类数据结构，但也可以 CDQ 分治。

设当前分治区间为 [l,r]，我们递归求完了 [l,mid] 和 [mid+1,r] 的答案，接下来要算这两部分之间的答案。

把 [l,mid] 的点看做修改操作（即插入），[mid+1,r] 的点看做查询，把整个区间按照 a_i 排序，直接双指针即可。

时间复杂度 \Theta(n\log n)。需要注意的是，每次内部直接排会导致复杂度多一只 \log，因此需要归并排序。

三维偏序：P3810

比上面多一个 c_i 属性。

先 CDQ 分治一次，变为二维偏序问题。上面提到可以直接树状数组（如果你不想写 CDQ 嵌套的话）。

CDQ 分治本来就需要一只 \log，树状数组还带来了另外一只 \log，因此总时间复杂度 \Theta(n\log^2n)。

本题还要记得去重及其他一些细节。

代码：

#include <bits/stdc++.h>
#define rep1(i,x,y) for (int i = (x);i <= (y);i++)
using namespace std;
const int N = 2e5 + 10;
int n,k,cnt;
int ans[N];
struct xxx
{
    int a;
    int b;
    int c;
    int ans;
    int cnt;
    bool operator<(const xxx& xx) { return a < xx.a || (a == xx.a && (b < xx.b || (b == xx.b && c < xx.c))); }
} a[N],tmp[N];
class fenwick
{
    int c[N];
    inline int lowbit(int x) { return x & (-x); }
    int sum(int x)
    {
        int ans = 0;
        for (;x > 0;x -= lowbit(x))
            ans += c[x];
        return ans;
    }
    public:
        fenwick() { memset(c,0,sizeof c); }
        int query(int l,int r) { return sum(r) - sum(l - 1); }
        void modify(int k,int x)
        {
            for (;k < N;k += lowbit(k))
                c[k] += x;
        }
} fen;
void cdq(int l,int r)
{
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    cdq(l,mid);
    cdq(mid + 1,r);
    int x = l;
    int y = mid + 1;
    int len = 0;
    while (x <= mid && y <= r)
        if (a[x].b <= a[y].b)
        {
            fen.modify(a[x].c,a[x].cnt);
            tmp[++len] = a[x++];
        }
        else
        {
            a[y].ans += fen.query(1,a[y].c);
            tmp[++len] = a[y++];
        }
    while (x <= mid)
    {
        fen.modify(a[x].c,a[x].cnt);
        tmp[++len] = a[x++];
    }
    while (y <= r)
    {
        a[y].ans += fen.query(1,a[y].c);
        tmp[++len] = a[y++];
    }
    rep1(i,l,mid)
        fen.modify(a[i].c,-a[i].cnt);
    rep1(i,1,len)
        a[i + l - 1] = tmp[i];
}
void solve()
{
    cin >> n >> k;
    rep1(i,1,n)
    {
        cin >> a[i].a >> a[i].b >> a[i].c;
        a[i].cnt = 1;
    }
    sort(a + 1,a + n + 1);
    cnt = 1;
    rep1(i,2,n)
        if (a[i].a == a[cnt].a && a[i].b == a[cnt].b && a[i].c == a[cnt].c)
            a[cnt].cnt++;
        else
            a[++cnt] = a[i];
    cdq(1,cnt);
    rep1(i,1,cnt)
        ans[a[i].ans + a[i].cnt - 1] += a[i].cnt;
    rep1(i,0,n - 1)
        cout << ans[i] << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

四维偏序

再加了一个 d_i 属性。

这里就需要 CDQ 分治的嵌套技巧了。写一个 CDQ 分治可以干掉一个维度，在 CDQ 分治中套另一个 CDQ 分治解三维偏序即可。时间复杂度 \Theta(n\log^3n)。

可以发现，每进行一次 CDQ 分治即可以多一只 \log 的时间代价解决一个维度的偏序，不过 \Theta(n\log^4n) 及以上实际跟平方做法已经跑得差不多了，所以更高维的偏序 CDQ 分治其实并不具有优势。（当然也不可能有出题人出这种无聊题）

更多例题：

P4514 加强版

给定一个矩阵，初始所有元素为 0，支持子矩阵加和子矩阵求和查询。

原题的数据范围直接用二维树状数组就能过。但其实可以用 CDQ 分治解决该题 n,m\le 2\times10^5 的强化版。

考虑一个俗称“Super BIT”的 trick：设差分数组 d_{x,y}=a_{x,y}-a_{x-1,y}-a_{x,y-1}+a_{x-1,y-1}，前缀和数组 sum_{x,y}=\sum_{i=1}^x\sum_{j=1}^y a_{i,j}，推式子可得 sum_{x,y}=\sum_{i=1}^x\sum_{j=1}^y d_{i,j}\times((x+1)\times(y+1)-(x+1)\times j-(y+1)\times i+i\times j)。

把这个式子拆成 4 部分累加求解。我们相当于只需解决一个三个维度分别为时间、x 坐标、y 坐标的三维偏序问题，CDQ 分治求解即可。

代码：

#include <bits/stdc++.h>
//#define MULTITEST
using namespace std;
typedef long long ll;
#define y1 __y1__
#define rep1(i,x,y) for (int i = (x);i <= (y);i++)
#define rep2(i,x,y) for (int i = (x);i >= (y);i--)
#define rep3(i,x,y,z) for (int i = (x);i <= (y);i += (z))
#define rep4(i,x,y,z) for (int i = (x);i >= (y);i -= (z))
#define cl(a) memset(a,0,sizeof(a))
const int N = 2050;
const int M = 2e5 + 10;
char ch;
int n,m,qcnt,x1,y1,x2,y2,delta;
struct query
{
    int id;
    int x;
    int y;
    int val;
    int op;
} q[M << 2],tmp[M << 2];
int f[N],fi[N],fj[N],fij[N],ans[M];
bool isquery[M];
inline int lowbit(int x) { return x & (-x); }
void modify(int a[],int k,int x)
{
    for (;k < N;k += lowbit(k))
        a[k] += x;
}
int query(int a[],int k)
{
    int ans = 0;
    for (;k > 0;k -= lowbit(k))
        ans += a[k];
    return ans;
}
inline void rmodify(int x,int y,int val)
{
    modify(f,y,val);
    modify(fi,y,val * x);
    modify(fj,y,val * y);
    modify(fij,y,val * x * y);
}
inline int rquery(int x,int y) { return query(f,y) * (x + 1) * (y + 1) - query(fi,y) * (y + 1) - query(fj,y) * (x + 1) + query(fij,y); }
void cdq(int l,int r)
{
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    cdq(l,mid);
    cdq(mid + 1,r);
    int x = l;
    int y = mid + 1;
    int len = 0;
    for (;y <= r;y++)
    {
        for (;x <= mid && q[x].x <= q[y].x;x++)
        {
            tmp[++len] = q[x];
            if (q[x].op == 0)
                rmodify(q[x].x,q[x].y,q[x].val);
        }
        tmp[++len] = q[y];
        if (q[y].op == 1)
            ans[q[y].id] += q[y].val * rquery(q[y].x,q[y].y);
    }
    for (;x <= mid;x++)
        tmp[++len] = q[x];
    for (x = l;x <= mid && q[x].x <= q[r].x;x++)
        if (q[x].op == 0)
            rmodify(q[x].x,q[x].y,-q[x].val);
    rep1(i,1,len)
        q[l + i - 1] = tmp[i];
}
void solve()
{
    cin >> ch >> n >> m;
    int qaq = 0;
    while (cin >> ch >> x1 >> y1 >> x2 >> y2)
    {
        qaq++;
        if (ch == 'L')
        {
            cin >> delta;
            q[++qcnt] = {qaq,x1,y1,delta,0};
            if (x2 < n && y2 < m)
                q[++qcnt] = {qaq,x2 + 1,y2 + 1,delta,0};
            if (x2 < n)
                q[++qcnt] = {qaq,x2 + 1,y1,-delta,0};
            if (y2 < m)
                q[++qcnt] = {qaq,x1,y2 + 1,-delta,0};
        }
        else
        {
            q[++qcnt] = {qaq,x2,y2,1,1};
            if (x1 > 1 && x2 > 1)
                q[++qcnt] = {qaq,x1 - 1,y1 - 1,1,1};
            if (x1 > 1)
                q[++qcnt] = {qaq,x1 - 1,y2,-1,1};
            if (y1 > 1)
                q[++qcnt] = {qaq,x2,y1 - 1,-1,1};
            isquery[qaq] = true;
        }
    }
    cdq(1,qcnt);
    rep1(i,1,qaq)
        if (isquery[i])
            cout << ans[i] << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
#ifdef MULTITEST
    cin >> t;
#else
    t = 1;
#endif
    while (t--)
        solve();
}

P3157

给定序列，每次删除一个元素，求出删除前序列总逆序对数量。

先求出原始逆序对，然后考虑如何计算每次减少的逆序对数量。

对于每次删的元素，消失的逆序对为以下两者之一：

• 在它前面，权值比他大，且删去时间比他晚
• 在它后面，权值比他小，且删去时间比他晚

每个点有权值、位置、删除时间三个量，就是三维偏序，CDQ 分治求解。

代码：

#include <bits/stdc++.h>
//#define MULTITEST
using namespace std;
typedef long long ll;
#define int ll
#define rep1(i,x,y) for (int i = (x);i <= (y);i++)
#define rep2(i,x,y) for (int i = (x);i >= (y);i--)
#define rep3(i,x,y,z) for (int i = (x);i <= (y);i += (z))
#define rep4(i,x,y,z) for (int i = (x);i >= (y);i -= (z))
#define cl(a) memset(a,0,sizeof(a))
const int N = 1e5 + 10;
int n,q,tp,ans;
struct xxx
{
    int val;
    int del;
    int ans;
    bool operator<(const xxx& xx) { return val < xx.val; }
} a[N],tmp[N];
bool cmp(const xxx& xx,const xxx& yy) { return xx.del < yy.del; }
int rev[N];
class fenwick
{
    int c[N];
    inline int lowbit(int x) { return x & (-x); }
    int sum(int x)
    {
        int ans = 0;
        for (;x > 0;x -= lowbit(x))
            ans += c[x];
        return ans;
    }
    public:
        void clr() { cl(c); }
        int query(int l,int r) { return sum(r) - sum(l - 1); }
        void modify(int k,int x)
        {
            for (;k <= n + 1;k += lowbit(k))
                c[k] += x;
        }
} fen;
void cdq(int l,int r)
{
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    cdq(l,mid);
    cdq(mid + 1,r);
    int x = l;
    int y = mid + 1;
    while (x <= mid)
    {
        while (a[x].val > a[y].val && y <= r)
            fen.modify(a[y++].del,1);
        a[x].ans += fen.query(a[x].del + 1,q + 1);
        x++;
    }
    x = l;
    y = mid + 1;
    while (x <= mid)
    {
        while (a[x].val > a[y].val && y <= r)
            fen.modify(a[y++].del,-1);
        x++;
    }
    x = mid;
    y = r;
    while (y > mid)
    {
        while (a[y].val < a[x].val && x >= l)
            fen.modify(a[x--].del,1);
        a[y].ans += fen.query(a[y].del + 1,q + 1);
        y--;
    }
    x = mid;
    y = r;
    while (y > mid)
    {
        while (a[y].val < a[x].val && x >= l)
            fen.modify(a[x--].del,-1);
        y--;
    }
    sort(a + l,a + r + 1);
}
void solve()
{
    cin >> n >> q;
    rep1(i,1,n)
    {
        cin >> a[i].val;
        rev[a[i].val] = i;
        a[i].del = q + 1;
    }
    rep1(i,1,q)
    {
        cin >> tp;
        a[rev[tp]].del = i;
    }
    fen.clr();
    rep1(i,1,n)
    {
        ans += fen.query(a[i].val + 1,n + 1);
        fen.modify(a[i].val,1);
    }
    fen.clr();
    cdq(1,n);
    sort(a + 1,a + n + 1,cmp);
    rep1(i,1,q)
    {
        cout << ans << '\n';
        ans -= a[i].ans;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
#ifdef MULTITEST
    cin >> t;
#else
    t = 1;
#endif
    while (t--)
        solve();
}

P4169

初始平面上有一些点。支持添加一个点，和查询距离某个位置最近的点。此处距离指曼哈顿距离。

• 考察右指针 r：对于每个块都要跑一遍整个序列，共 n\times\dfrac{n}{B}=\dfrac{n^2}{B}
• 考察时间 t：对于每对左右端点，时间戳都可能从 0 跑到 m_2，共 (\dfrac{n}{B})^2\times m_2=\dfrac{m_2n^2}{B^2}

而题目中几乎不可能分别保证 m_1,m_2 的范围，因此可以假定 m_1,m_2 同阶。设 m=m_1=m_2，总复杂度为 \Theta(mB+\dfrac{n^2}{B}+\dfrac{mn^2}{B^2})。

如果不假定 n,m 同阶，这个东西貌似也能做，但是极其复杂，推出来的柿子很丑。所以假定 n,m 同阶，复杂度为 \Theta(nB+\dfrac{n^2}{B}+\dfrac{n^3}{B^2})。

因为 B<n，所以 \dfrac{n^2}{B}<\dfrac{n^3}{B}，因此原式 =\Theta(nB+\dfrac{n^3}{B^2})。

• 法一：该式的导数是 n-\dfrac{2n^3}{B^3}。令其 =0，此时 B=\sqrt[3]{2n^2}=\Theta(n^{\frac{2}{3}})。带回原式得 n^{\frac{5}{3}}。
• 法二：（感谢@Sunrise_beforeglow 指出）可以用把式子拆了之后用三元均值不等式，原式 =\dfrac{nB}{2}+\dfrac{nB}{2}+\dfrac{n^3}{B^2}\ge3\times\sqrt[3]{\dfrac{nB}{2}\times\dfrac{nB}{2}\times\dfrac{n^3}{B^2}}=\Theta(n^{\frac{5}{3}})。

至此，我们终于推导出了当 B=n^{\frac{2}{3}} 时，取得最优复杂度 n^{\frac{5}{3}}。

代码：

#include <bits/stdc++.h>
//#define MULTITEST
using namespace std;
typedef long long ll;
#define rep1(i,x,y) for (int i = (x);i <= (y);i++)
#define rep2(i,x,y) for (int i = (x);i >= (y);i--)
#define rep3(i,x,y,z) for (int i = (x);i <= (y);i += (z))
#define rep4(i,x,y,z) for (int i = (x);i >= (y);i -= (z))
#define cl(a) memset(a,0,sizeof(a))
const int N = 1e6 + 10;
const int B = 2610;
int n,m,x,y,cnt1,cnt2,anss;
char ch;
int a[N],in[N],ans[N],buc[N];
struct query
{
    int l;
    int r;
    int t;
    int id;
    bool operator<(const query& xx) const
    {
        if (in[l] != in[xx.l])
            return in[l] < in[xx.l];
        if (in[r] != in[xx.r])
            return in[r] < in[xx.r];
        return t < xx.t;
    }
} q[N];
struct modify
{
    int pos;
    int val;
} c[N];
inline void add(int x) { anss += (++buc[x] == 1); }
inline void del(int x) { anss -= (--buc[x] == 0); }
inline void work(int now,int i)
{
    if (c[now].pos >= q[i].l && c[now].pos <= q[i].r)
    {
        add(c[now].val);
        del(a[c[now].pos]);
    }
    swap(c[now].val,a[c[now].pos]);
}
void solve()
{
    cin >> n >> m;
    rep1(i,1,n)
    {
        cin >> a[i];
        in[i] = (i - 1) / B + 1;
    }
    rep1(i,1,m)
    {
        cin >> ch >> x >> y;
        if (ch == 'Q')
            q[++cnt1] = {x,y,cnt2,cnt1};
        else
            c[++cnt2] = {x,y};
    }
    sort(q + 1,q + cnt1 + 1);
    int l = 1;
    int r = 0;
    int t = 0;
    rep1(i,1,cnt1)
    {
        while (l > q[i].l)
            add(a[--l]);
        while (r < q[i].r)
            add(a[++r]);
        while (l < q[i].l)
            del(a[l++]);
        while (r > q[i].r)
            del(a[r--]);
        while (t < q[i].t)
            work(++t,i);
        while (t > q[i].t)
            work(t--,i);
        ans[q[i].id] = anss;
    }
    rep1(i,1,cnt1)
        cout << ans[i] << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
#ifdef MULTITEST
    cin >> t;
#else
    t = 1;
#endif
    while (t--)
        solve();
}