离线算法

2025-10-09T23:11:06+08:00 | 9分钟阅读 | 更新于 2025-10-09T23:11:06+08:00

@
离线算法

充满爱了捏。

分治

CDQ 分治

简单来说，就是每次将序列分成 $[l,r]$ 分成 $[l,mid],[mid+1,r]$ 两部分。

对于属于 $[l,mid]$ 与 $[mid+1,r]$ 的部分，递归计算即可。

对于跨越 $mid$ 的部分，就是递归所处理的，假设对于 $n=r-l+1$，处理这部分的复杂度为 $\mathcal O(nk)$，则总复杂度 $T(n)=2T(n/2)+\mathcal O(nk)=\mathcal O(kn\log n)$。

如果几个维度中不存在 $A_i\le A_j$ 的形式，那么可以随便选一维 $A_i\le B_j$，建 $n$ 个虚点使 $A_i=B_i$，直接求虚点的答案即可。

P3350 [ZJOI2016] 旅行者

给出网格图，每个点 $(i,j)$ 向上向右（也可以向下左走）都有代价 $c(i,j),r(i,j)$。$q$ 次询问，查询 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的最小代价。

$n\times m\le 2\times 10^4,q\le 10^5$。

其实可以视作一种「矩形分治」。

设分治函数 $(x_1,y_1,x_2,y_2)$ 表示仅当前考虑的是以 $(x_1,y_1),(x_2,y_2)$ 为顶点的矩形，处理所有在这个矩形内的询问。

不妨取 $n$ 轴中线，并处理出该区域内所有点到中线上所有点的最短路。则询问可以被分为：

  • $x_1,x_2$ 跨越中线。显然，无论如何走，这两个点必然要跨越中线，故这对询问的答案就是枚举跨越中线某个点的最小值。

  • $x_1,x_2$ 不跨越中线。那么有两种情况，一种是跨越当前中线，一种是不跨越。对此类进行询问即可。

为什么是对的？考虑跨越中线的实际意义，即在中线另一端的询问，如果要考虑穿越该中线的贡献，则区域是固定的。每一次矩形范围的缩小，实际上是对答案范围的减小，这保证了每次不会走多余，故答案是正确的。

然后是复杂度的相关

优化 DP

P4093 [HEOI2016/TJOI2016] 序列

给出序列 $a_i$，$m$ 次独立的变化 u v：$a_u\gets v$。求使得任意版本都满足的最长不下降子序列。

转移式具有三维的偏序关系：$j<i,mx_j\le a_i,a_j\le mn_i$，其中 $mx_i$ 表示所有变换中 $i$ 的最大值，$mn_i$ 表示所有变换中 $j$ 的最小值。

当且仅当满足这个关系，才能有递推关系：$f(i)=f(j)+1$，$f(i)$ 表示以 $i$ 结尾的最长上升子序列长度。

对于当前的区间 $[l,r]$，考虑先递归计算 $[l,mid]$ 的部分。再计算从 $[l,mid]$ 转移到 $[mid+1,r]$ 的部分。最后递归计算 $[mid+1,r]$ 的部分。对于跨中点部分，先对数据按照 $a_i$ 排序，然后用数据结构维护前缀最大值即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

void divide (int l, int r) {
    if (l == r) return f[l] = max (f[l], 1), void ();
    int mid = l + r >> 1;
    divide (l, mid); 
    
    for (int i = l; i <= r; i ++) tmp[i] = p[i];
    sort (p + l, p + mid + 1);
    sort (p + mid + 1, p + r + 1); 
    for (int i = mid + 1, j = l; i <= r; i ++) {
        while (j <= mid && p[j].mx <= p[i].a) { t.ist (p[j].a, f[p[j].i]); j ++; }
        f[ p[i].i ] = max (f[ p[i].i ], t.qry (p[i].mn) + 1);
    }
    for (int i = l; i <= mid; i ++) t.del (p[i].a);
    for (int i = l; i <= r; i ++) p[i] = tmp[i];

    divide (mid + 1, r);
}

注意这里的 $f(i)$ 需要是原始下标。

「启发式分裂」/ 最值分治

CF1156E Special Segments of Permutation

给出排列 $p$。求满足 $p_l+p_r=\max\limits_{i\in[l,r]}p_i$ 的子区间个数。

一个显然的做法是，对所有数求出其为最大值的子区间。即对于每个数用单调栈求出 $L_i,R_i$ 分别表示向左/右最远的使 $p_{L_i/R_i}<p_i$ 的数。

下一步选择左右任意一个区间枚举，复杂度就是 $\mathcal O(n^2)$ 了。

我们不妨研究一下这个结构。把这个排列放在大根堆笛卡尔树上，对于 $[L_i,i)$ 就是构成 $i$ 的左子树的所有元素，$(i,R_i]$ 就是构成其右子树的所有元素。根据启发式合并的思想，每次暴力合并当前根的较小子树到较大子树上时，总复杂度是 $\mathcal O(n\log n)$ 的。那么相反，对笛卡尔树进行「启发式分裂」，复杂度依然为 $\mathcal O(n\log n)$。

我们套用这个思想，每次遍历管辖区间的较小区间，复杂度亦可降到 $\mathcal O(n\log n)$。

P5979 [PA 2014] Druzyny

给出 $n$ 个数，把每个数划分到有 $[c_i,d_i]$ 个数的组（每个组内元素编号连续）里。求最大组数，以及对应方案数。

$n\le 10^6$。

设 $f_i,g_i$ 分别表示划分到 $i$ 的最大组数以及对应方案数，显然有转移式：$f_i=1+\max\limits_{\max\limits_{k\in(j,i]} c_k\le i-j\le\min\limits_{k\in(j,i]}d_k}f_k$，$g_i=\sum\limits_{\max\limits_{k\in(j,i]} c_k\le i-j\le\min\limits_{k\in(j,i]}d_k\and f_i=f_j+1}g_j$。$g$ 的转移和 $f$ 是同时的，因此可以用一个类将二者绑定起来同时转移。

设 $range(l,r)=\left[\max\limits_{i\in[l,r]}c_i,\min\limits_{i\in[l,r]}d_i\right]$。考虑分治，对于 $[l,r]$ 区间，假设已经求出 $i\in[l,mid]$，考虑这部分到 $j\in(mid,r]$ 的贡献，设 $l_{i,j}=\max\limits_{k\in[i,j]}c_k$，$r_{i,j}=\min\limits_{k\in[i,j]}d_k$。对于可以转移的，必然满足如下条件。

  1. $j-i\in range(i,mid)\iff j\in\left[i+l_{i,mid},i+r_{i,mid}\right]$
  2. $j-i\in range (mid+1,j)\iff i\in\left[ j-r_{mid+1,j},j-l_{mid+1,j} \right]$

第一个条件是对 $j$ 的限制，第二个条件是对 $i$ 的限制。对于第二个限制，考虑开一棵线段树来查询。对于第一个限制，考虑扫描线。

具体来说，对于 $j=i+l_{i,mid}$，在线段树中插入 $i$ 位置上的元素。对于 $j=i+r_{i,mid}+1$，在线段树上删掉 $i$ 位置的贡献。

  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

#include <vector>
#include <iostream>

#define mid (l + r >> 1)

using namespace std;

const int N = 1e6 + 10;
const int P = 1e9 + 7;
const int inf = 1e9;

inline int add (int u, int v) {
    u += v;
    if (u >= P) u -= P;
    if (u < 0) u += P;
    return u;
}

struct data {
    int f, g;
    data (int f = -inf, int g = 0) : f(f), g(g) {}
};

inline data get (data x, data y) {
    if (x.f == y.f) return data (x.f, add (x.g, y.g));
    return x.f > y.f ? x : y;
}

int n;
int c[N], d[N], L[N], R[N];
data f[N];
vector <int> scanl[N];

struct SegmenTree {
    data t[N << 2];

    #define ls (u << 1)
    #define rs (u << 1 | 1)

    void pushup (int u) { t[u] = get (t[ls], t[rs]); }
    void modify (int u, int l, int r, int qq, data k) {
        if (qq > r || qq < l) return;
        if (l == r) return t[u] = k, void (); 
        if (qq <= mid) modify (ls, l, mid, qq, k);
        else           modify (rs, mid + 1, r, qq, k);
        pushup (u);
    }
    
    data query (int u, int l, int r, int ql, int qr) {
        if (ql > qr) return data ();
        if (l >= ql && r <= qr) return t[u];
        data ret = data ();
        if (mid >= ql) ret = get (ret, query (ls, l, mid, ql, qr));
        if (qr > mid)  ret = get (ret, query (rs, mid + 1, r, ql, qr));
        return ret;
    }
} sgt;

void divide (int l, int r) {
    if (l == r) return ;
    
    divide (l, mid); for (int i = mid + 1; i <= r + 1; i ++) scanl[i].clear ();

    int mxl = 1, mnr = n; 
    for (int i = mid; i >= l; i --) {
        L[i] = mxl + i, R[i] = mnr + i;
        if (mxl > mnr || R[i] <= mid) break ;
        if (L[i] <= r)
            scanl[max (mid + 1, L[i])].push_back (i),
            scanl[min (r + 1, R[i] + 1)].push_back (i + N);
        mxl = max (mxl, c[i]), mnr = min (mnr, d[i]);
    }

    mxl = 1, mnr = n;
    for (int j = mid + 1; j <= r; j ++) {
        for (const auto& p : scanl[j]) {
            if (p < N) sgt.modify (1, 0, n, p, f[p]);
            else       sgt.modify (1, 0, n, p - N, data ());
        }
        mxl = max (c[j], mxl), mnr = min (d[j], mnr);
        if (mnr < mxl || j - mnr > mid) break;
        auto res = sgt.query (1, 0, n, max (l, j - mnr), min (mid, j - mxl)); res.f ++;
        f[j] = get (f[j], res);
    } 

    for (int i = l; i <= mid; i ++) sgt.modify (1, 0, n, i, data ());

    divide (mid + 1, r);
}

int main (void) {

    scanf ("%d", &n);
    for (int i = 1; i <= n; i ++) scanf ("%d%d", c + i, d + i);
    
    f[0] = data (0, 1); 
    divide (0, n);

    if (f[n].f < 0) puts ("NIE");
    else printf ("%d %d\n", f[n].f, f[n].g);

    return 0;
}

线段树分治

是一种离线算法，通常用于处理可以加入但难以撤销的数据结构的问题。

核心思想是在 时间轴 上建线段树，对于加入操作相当于在 $[l,r]$ 这段时间内打标记。这实际上是 标记永久化 的 Trick，也就是不下传标记。

具体来说，遍历整棵线段树，在叶子节点统计贡献，回溯时撤销操作。

P5787 二分图 /【模板】线段树分治

给出 $n$ 个节点的图，有 $m$ 条边，出现的时间段不同。求每个时刻该图是否为二分图。

首先，二分图一个很好的可以用于动态的判定方法就是扩展域并查集：

  • 二分图相当于给所有相邻点染不同色，且总共只有两种颜色。设 $i$ 为集合 $S$，$i+n$ 为集合 $T$。这样就表示了 $i$ 的两种颜色。一个加边操作 $(u,v)$ 相当于在并查集加边 $(u,v+n),(v,u+n)$，这样就表示了 $u$ 与 $v$ 异色。若存在 $u,u+n$ 在同一个集合时，矛盾，即非二分图。

但是并查集的撤销操作不好做，于是考虑线段树分治。每条边相当于在 $[l,r]$ 时间出现，直接在时间轴上打标记，表示这一段时间内有这条边。体现在线段树上，就是加入当前节点的标记，遍历完子节点后删除。删除操作就相当于删掉这一条边，也就是将合并二者复原，所以要用按秩合并的并查集。

 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

void modify (int u, int l, int r, int ql, int qr, pii w) {
    if (l >= ql && r <= qr) return v[u].push_back (w), void ();
    if (ql <= mid) modify (ls, l, mid, ql, qr, w);
    if (mid < qr) modify (rs, mid + 1, r, ql, qr, w);
}

int fa[N << 1], sz[N << 1];
int find (int x) { return fa[x] == x ? x : find (fa[x]); }

void del (vector <pii> w) {
    for (auto [x, y] : w) sz[x] -= sz[y], fa[y] = y;
}

void query (int u, int l, int r) {
    vector <pii> upd;
    if (cheq[u]) {
        for (auto& [x, y] : v[u]) {
            int dx = x + n, dy = y + n;
            x = find (x), y = find (y), dx = find (dx), dy = find (dy);
            if (x == y) { cheq[u] = false; break ; }
            if (sz[x] < sz[dy]) swap (x, dy);
            if (sz[y] < sz[dx]) swap (y, dx);
            upd.push_back ({x, dy}), upd.push_back ({y, dx});
            sz[x] += sz[dy], sz[y] += sz[dx];
            fa[dy] = x, fa[dx] = y;
        }
    }
    if (l == r) return puts (cheq[u] ? "Yes" : "No"), del (upd), void ();
    cheq[ls] = cheq[rs] = cheq[u];
    query (ls, l, mid); query (rs, mid + 1, r); del (upd);
}

int main (void) {

    scanf ("%d%d%d", &n, &m, &k);for (int i = 1; i <= 2 * n; i ++) fa[i] = i, sz[i] = 1; cheq[1] = 1;
    while (m --) {
        int x, y, l, r; scanf ("%d%d%d%d", &x, &y, &l, &r);
        modify (1, 1, k, l + 1, r, {x, y});
    } 
    query (1, 1, k);

    return 0;
}

P5227 [AHOI2013] 连通图

给出无向连通图和 $k$ 个元素不超过 $4$ 的集合 $s$。每次删除 $s$ 内的边，询问图是否仍然联通。每次询问独立。

直接转化一下就成上道题了。

对每条边记录出现的时间段，然后就转化成上一道题了。这里说一下为什么这样复杂度是对的。

可以发现，最多有 $4k$ 条边被删除。假设每条边被划分成的时间段数为 $p$，注意到这个 $p$ 最大就是 $8k$。而一段时间段最多被 $\log n$ 条边表示，因此上界是 $8k\log n<10^7$，而且这是一个很松的上界。也就是每个节点 vector 维护的边最多是不到 $10^7$，所以是对的。

还有一点细节，就是撤销的顺序。需要按照从后往前（就是栈的顺序）来删：若从前往后，假设 $u$ 是 $v$ 的父节点，下一步 $w$ 成为 $u$ 的父节点。那么删除顺序是 $sz_u\gets sz_u-sz_v$，$sz_w\gets sz_w-sz_u=sz_w-sz_u+sz_v$，会导致少删。因此要从后往前。

整体二分

将所有的询问离线下来，对于操作统一询问与回答。

考虑一个询问，至多会被操作算 $\log n$ 次，故递归的复杂度是 $\mathcal O(n\log n)$。

处理这段区间实际上可以上一个状态转移，设当前区间为 $[l,r]$，次数也就是为 $\left\lfloor\dfrac{l+r}2\right\rfloor$，维护一个指针表示当前算到哪了。按照固定的顺序 $[l,mid]\to[mid+1,r]$，考虑相邻层 $mid$ 之差，即相邻状态转移的复杂度。若 $l+1=r$，则 $\Delta mid=1$。递归时，$mid$ 与 $l$ 的长度不断减半。回溯后，每次 $mid$ 逐层倍增，和减半是相同的。故只需考虑减半，即 $T(n)=2T(n/2)+\mathcal O(n)$，有 $T(n)=\mathcal O(n\log n)$。即相邻状态的转移也是 $\log n$ 级别的。

P3527 [POI 2011] MET-Meteors

$n$ 个国家，$m$ 段。每一段是一个国家的殖民地。

第 $i$ 个国家期望有 $p_i$ 个陨石。

$Q$ 天降陨石，每次形如 l r v，指区间 $[l,r]$（若 $l>r$，则是 $[l,n]\cup[1,r]$）降下 $v$ 个陨石。

对于每个国家，求最少天，使期望达到。

$n,m,Q\le 3\times 10^5$。

你看，和上面所说的做法是不是一模一样？

维护区间的差分数组，单点修改区间查询。就做完了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

void divide (int l, int r, int ql, int qr) {
    int mid = ql + qr >> 1;
    int c1 = 0, c2 = 0;
    if (ql == qr) {
        for (int i = l; i <= r; i ++) ans[ctry[i]] = ql;
        return ;
    } 
    while (now < mid) modify (++ now, 1); while (now > mid) modify (now --, -1);
    for (int i = l; i <= r; i ++) {
        ll res = 0; int nowc = ctry[i];
        for (auto v : cotry[nowc]) res += t.qry (v);
        if (res >= p[nowc]) wctry[++ c1] = nowc;
        else                wwctry[++ c2] = nowc;
    }
    for (int i = 1; i <= c1; i ++) ctry[l + i - 1] = wctry[i];
    for (int i = 1; i <= c2; i ++) ctry[l + c1 + i - 1] = wwctry[i];
    if (c1) divide (l, l + c1 - 1, ql, mid);
    if (c2) divide (l + c1, l + c1 + c2 - 1, mid + 1, qr);
}

调用时 divide (1, n, 1, q+1)，其中 q+1 是给不合法的情况。

© 2025 Toorean's Blog

🌱 Powered by Hugo with theme Dream.