历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

离线算法之 cdq 分治

作者：

Union_Find , 2025-06-11 20:21:34 · 福建 , 所有人可见 , 阅读 7

0.前言

~~膜拜 cdq 大神。~~

cdq 分治实际上就是分治，主要思想是把一个问题分成两个子问题，然后处理跨过中间的问题。

当然这是离线算法，如果强制在线就炸了。

1.多维偏序

【模板】三维偏序（陌上花开）

如标题所示，这是一道模板题。他要我们求出对于每个 $i$ 满足 $a_j \le a_i,b_j \le b_i,c_j \le c_i$ 的 $j$ 的个数。

如果只有两维，我们可以用归并排序或树状数组来处理。但是这题如果直接用树状数组那就要树套树了，时间复杂度 $O(n\log^2n)$，空间复杂度 $O(n\log n)$，主要是空间，很多题里是开不下的，常数也很大。

我们来回忆一下归并排序的过程。我们排序区间 $[l,r]$ 的时候，先取了中点 $mid$，然后对 $[l,mid]$ 以及 $[mid+1,r]$ 排序。这时候，我们就要归并了。我们归并的时候可以容易地得到对于 $[mid+1,r]$ 中的每一个 $i$，在 $[l,mid]$ 中有多少个数比他小。此时我们就相当于求了跨过中间的问题。所以归并排序求逆序对（即二维偏序）本质上就是cdq 分治。

现在我们考虑多了一维。在二维的时候，我们仅仅只需要用双指针就可以轻松的得到答案。但是现在又多了一维，此时仅靠分治和双指针是不够了，我们需要支持动态加点，动态查询比某个数小的数的个数。这个简单，只要用树状数组即可。

考虑我们先按照 $a$ 排序，然后分成两部分，递归处理。接下来处理跨过中间的个数。我们把两部分都按照 $b$ 排序。此时我们发现，因为一开始按照 $a$ 排序，所以左边所有 $a$ 都小于右边的 $a$，已经满足了一个偏序关系。然后我们双指针，可以满足另一个偏序关系。然后我们在移动左边指针时，将 $c$ 加入树状数组，然后对于右边每一个位置查询个数即可。

考虑时间复杂度，每一层都是 $O(n\log n)$，根据主定理，得到 $T(n) = 2T(\frac n 2) + O(n\log n) = O(n\log^2n)$。

现在看一下代码。

struct Point{
    int a, b, c, id;
}pt[N], p[N];
bool operator <(const Point &x, const Point &y){return (x.a != y.a) ? x.a < y.a : (x.b != y.b) ? x.b < y.b : x.c < y.c;}
bool operator ==(const Point &x, const Point &y){return x.a == y.a && x.b == y.b && x.c == y.c;}
il bool cmp(Point x, Point y){return (x.b != y.b) ? x.b < y.b : (x.a != y.a) ? x.a < y.a : x.c < y.c;}
il void cdq(int l, int r){
    if (l == r) return ;
    int mid = (l + r) >> 1;
    cdq(l, mid), cdq(mid + 1, r);// 我们一开始在外面先按照 a 排序
    sort(p + l, p + mid + 1, cmp), sort(p + mid + 1, p + r + 1, cmp);// 两边按照 b 排序
    int i, j;
    for (i = l - 1, j = mid + 1; j <= r; j++){
        while (p[i + 1].b <= p[j].b && i < mid) i++, add(p[i].c, ct[p[i].id]);// 将 c 加入树状数组，这里 ct 表示的是重复元素的个数
        ans[p[j].id] += ask(p[j].c);
    }
    for (int k = l; k <= i; k++) add(p[k].c, -ct[p[k].id]);// 清空树状数组
}

对于这题，会有重复的元素，所以要在外面去重。

现在你会了最简单的多维偏序问题，来看一下更难的。

Mokia 摩基亚

要支持单点加，查询矩阵点权和，横纵坐标是 $10^5$。

由于卡空间，所以我们不能用树套树，只能用 cdq 分治。

我们转化一下，首先可以差分一下，把矩阵的左下角固定在 $(1,1)$ 处。这样子我们就只要查询有多少个点在查询点的左下角。

现在我们设加入的点是 $(a_i,b_i)$，加入时间是 $t1_i$，查询点是 $(x,y)$，查询时间是 $t2$，我们就是查询满足下面条件的点的个数。

$t1_i < t2$。
$a_i \le x$。
$b_i \le y$。

发现这就是三位偏序，套板子即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
#define N 2000006
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n, m, cnt, tr[N], ans[N];
int op;
il void add(int x, int k){for (int i = x; i <= N - 5; i += (i & (-i))) tr[i] += k;}
il int ask(int x){int ans = 0;for (int i = x; i >= 1; i -= (i & (-i))) ans += tr[i];return ans;}
struct Point{
    int a, b, c, t, id, val;
}p[N];
bool operator <(const Point &x, const Point &y){return (x.a != y.a) ? x.a < y.a : (x.b != y.b) ? x.b < y.b : x.c < y.c;}
il bool cmp(Point x, Point y){return (x.b != y.b) ? x.b < y.b : (x.a != y.a) ? x.a < y.a : x.c < y.c;}
il void cdq(int l, int r){
    if (l == r) return ;
    int mid = (l + r) >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    sort(p + l, p + mid + 1, cmp), sort(p + mid + 1, p + r + 1, cmp);
    int i, j;
    for (i = l - 1, j = mid + 1; j <= r; j++){
        while (p[i + 1].b <= p[j].b && i < mid) i++, add(p[i].c, p[i].t);
        ans[p[j].id] += ask(p[j].c) * p[j].val;
    }
    for (int k = l; k <= i; k++) add(p[k].c, -p[k].t);
}
signed main(){
    op = rd(), m = rd() + 1, cnt = 0;
    for (;;){
        op = rd();
        if (op == 3) break;
        if (op == 1) n++, p[n] = Point{n, rd() + 1, rd() + 1, rd(), 0, 0};
        if (op == 2){
            int ax = rd() + 1, ay = rd() + 1, bx = rd() + 1, by = rd() + 1;
            cnt++;
            n++, p[n] = Point{n, bx, by, 0, cnt, 1};
            n++, p[n] = Point{n, bx, ay - 1, 0, cnt, -1};
            n++, p[n] = Point{n, ax - 1, by, 0, cnt, -1};
            n++, p[n] = Point{n, ax - 1, ay - 1, 0, cnt, 1};
        }
    }
    sort (p + 1, p + n + 1);
    cdq(1, n);
    for (int i = 1; i <= cnt; i++) printf ("%lld\n", ans[i]);
    return 0;
}

Why Did the Cow Cross the Road III

有一个两个长度为 $n$ 的排列，定义种类 $x$ 的线是连接第一个排列和第二排列中值为 $x$ 大的两个位置的线。求无序数对 $(i,j)$ 的个数，要满足 $i$ 的线和 $j$ 的线相交，且 $|i-j| > k$。

设 $x_i$ 表示 $i$ 在排列 $a$ 中的位置，$y_i$ 表示 $i$ 在排列 $b$ 中的位置。要让 $i,j$ 的线相交，不妨设 $x_i < x_j$，那么就有 $y_i > y_j$。

现在就是三个限制。

$x_i < x_j$。
$y_i > y_j$。
$|i-j|>k$，即 $i \not \in [j-k,j+k]$。

这三个限制前两个就是偏序，但是第三个似乎不是。不过我们可以发现在 cdq 分治的过程中，最后一维要用树状数组维护，树状数组本身就支持区间查询，所以一样可以 cdq 分治。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
#define N 100005
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n, k, a[N], b[N], x[N], y[N], id[N], tr[N], ans;
il bool cmp1(int a, int b){return x[a] < x[b];}
il bool cmp2(int a, int b){return y[a] > y[b];}
il void clr(int x){for (int i = x; i <= n; i += (i & (-i))) tr[i] = 0;}
il void add(int x, int k){for (int i = x; i <= n; i += (i & (-i))) tr[i] += k;}
il int ask(int x){int ans = 0;for (int i = x; i >= 1; i -= (i & (-i))) ans += tr[i];return ans;}
void cdq(int l, int r){
    if (l == r) return ;
    int mid = (l + r) >> 1;
    sort (id + l, id + r + 1, cmp1);
    cdq(l, mid), cdq(mid + 1, r);
    sort (id + l, id + mid + 1, cmp2), sort (id + mid + 1, id + r + 1, cmp2);
    for (int i = l, j = mid + 1; j <= r; j++){
        for (; i <= mid && y[id[i]] > y[id[j]]; i++) add(id[i], 1);
        if (id[j] - k > 1) ans += ask(id[j] - k - 1);// 树状数组查询
        if (id[j] + k < n) ans += ask(n) - ask(id[j] + k);
    }
    for (int i = l; i <= mid; i++) clr(id[i]);
}
signed main(){
    n = rd(), k = rd();
    for (int i = 1; i <= n; i++) id[i] = i;
    for (int i = 1; i <= n; i++) x[a[i] = rd()] = i;
    for (int i = 1; i <= n; i++) y[b[i] = rd()] = i;
    cdq(1, n);
    printf ("%lld\n", ans);
    return 0;
}

「DTOI-2」星之河

给定树，对于每个点求其子树内的二维偏序个数。

我们先刻画在子树内，不难想到用 dfs 序刻画，那么就有

$a_j \le a_i$。
$b_j \le b_i$。
$dfn_j \in [dfn_i + 1,dfn_i + sz_i - 1]$

其中 $dfn_i$ 和 $sz_i$ 表示 dfs 序和子树大小。同上一题，我们树状数组处理最后一个即可。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 200005
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n, u, v, et, R[N], B[N], dfn[N], sz[N], id[N], tr[N], ans[N];
vector <int> e[N];
void dfs(int u, int fa){
    dfn[u] = ++et, sz[u] = 1;
    for (int v : e[u]) if (v != fa) dfs(v, u), sz[u] += sz[v];
}
il bool cmp1(int x, int y){return R[x] != R[y] ? R[x] < R[y] : B[x] != B[y] ? B[x] < B[y] : dfn[x] > dfn[y];}
il bool cmp2(int x, int y){return B[x] < B[y];}
il void add(int x, int k){for (int i = x; i <= n; i += (i & (-i))) tr[i] += k;}
il int ask(int x){int ans = 0;for (int i = x; i >= 1; i -= (i & (-i))) ans += tr[i];return ans;}
il void clr(int x){for (int i = x; i <= n; i += (i & (-i))) tr[i] = 0;}
void cdq(int l, int r){
    if (l == r) return ;
    int mid = (l + r) >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    sort (id + l, id + mid + 1, cmp2), sort (id + mid + 1, id + r + 1, cmp2);
    for (int i = l, j = mid + 1; j <= r; j++){
        for (; i <= mid && B[id[i]] <= B[id[j]]; i++) add(dfn[id[i]], 1);
        ans[id[j]] += ask(dfn[id[j]] + sz[id[j]] - 1) - ask(dfn[id[j]] - 1);
    }
    for (int i = l; i <= mid; i++) clr(dfn[id[i]]);
}
signed main(){
    n = rd();
    for (int i = 1; i < n; i++) u = rd(), v = rd(), e[u].push_back(v), e[v].push_back(u);
    dfs(1, 0);
    for (int i = 1; i <= n; i++) R[i] = rd(), B[i] = rd(), id[i] = i;
    sort (id + 1, id + n + 1, cmp1);
    cdq(1, n);
    for (int i = 1; i <= n; i++) if (ans[i]) printf ("%d\n", ans[i]);
    return 0;
}

天使玩偶/SJY摆棋子

$m$ 次操作，支持加入点，查询所有加入的点到某个点的曼哈顿距离最小值。

定义 $(x_1,y_1)$ 和 $(x_2,y_2)$ 的曼哈顿距离是 $|x_1-x_2|+|y_1-y_2|$。

不难注意到，我们可以大力分讨，查询的时候查询在左下角，左上角，右下角，右上角四个方位的最小距离，这样子可以消掉绝对值。现在以左下角为例，考虑怎么求。

我们现在就是求在查询操作之前且 $x_1<x,y_1<y$ 的 $x_1+y_1$ 的最大值。这实际上是一个三位偏序，离线下来用 cdq 分治即可。时间复杂度 $O(n\log^2n)$。

其余位置可以用 $(M-x,y),(x,M-y),(M-x,M-y)$ 直接求得，这里 $M$ 是坐标上限。

但是这里有一些细节要处理。

只有修改操作的点才可以加入树状数组，查询的点是不行的。
树状数组要初始化为负无穷，如果是 $0$ 会默认加入了点 $(0,0)$。

~~然后大力谴责出题人卡常。~~

T 飞了，要卡常。

cdq 分治的时候每一层都要排序，考虑上一层已经排完序了，可以归并排序，直接用 C++ 自带的 merge(bg_1,ed_1,bg_2,ed_2,bg_3)，这个函数可以将两个有序数列有序合并。
如果当前不是查询操作，不用移动另一个指针，可以优化后面一段没有查询操作的情况。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 1000005
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n, m, ans[N], op[N], tr[N];
const int M = 1e6;
struct Point{
    int x, y, id;
}p[N], q[N], a[N];
bool operator <(const Point &a, const Point &b){return a.x != b.x ? a.x < b.x : a.y != b.y ? a.y < b.y : a.id < b.id;}
il void add(int x, int k){for (int i = x; i <= M; i += (i & (-i))) tr[i] = max(tr[i], k);}
il int ask(int x){int ans = -1e9;for (int i = x; i >= 1; i -= (i & (-i))) ans = max(ans, tr[i]);return ans;}
il void clr(int x){for (int i = x; i <= M; i += (i & (-i))) tr[i] = -1e9;}
void cdq(int l, int r){
    if (l == r) return ;
    int mid = (l + r) >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    int j = l;
    for (int i = mid + 1; i <= r; i++) if (op[p[i].id]){
        for (; j <= mid && p[j].x <= p[i].x; j++) if (!op[p[j].id]) add(p[j].y, p[j].x + p[j].y);
        ans[p[i].id] = min(ans[p[i].id], p[i].x + p[i].y - ask(p[i].y));
    }
    for (int i = l; i < j; i++) if (!op[p[i].id]) clr(p[i].y);
    merge(p + l, p + mid + 1, p + mid + 1, p + r + 1, q + l);
    for (int i = l; i <= r; i++) p[i] = q[i];
}
signed main(){
    n = rd(), m = rd();
    for (int i = 1; i <= M; i++) tr[i] = -1e9;
    for (int i = 1; i <= n; i++) a[i] = Point{rd() + 1, rd() + 1, i}, ans[i] = 1e9;
    for (int i = n + 1; i <= n + m; i++) op[i] = rd() - 1, a[i] = Point{rd() + 1, rd() + 1, i}, ans[i] = 1e9;
    for (int i = 1; i <= n + m; i++) p[i] = Point{a[i].x, a[i].y, i};
    cdq(1, n + m);
    for (int i = 1; i <= n + m; i++) p[i] = Point{M - a[i].x, a[i].y, i};
    cdq(1, n + m);
    for (int i = 1; i <= n + m; i++) p[i] = Point{a[i].x, M - a[i].y, i};
    cdq(1, n + m);
    for (int i = 1; i <= n + m; i++) p[i] = Point{M - a[i].x, M - a[i].y, i};
    cdq(1, n + m);
    for (int i = n + 1; i <= n + m; i++) if (op[i]) printf ("%d\n", ans[i]);
    return 0;
}

Sunčanje

依次给定 $n$ 个矩形，问对于每一个矩形是否存在在它后面的矩形与它有交。

下文我们令 $(ax_i,ay_i)$ 表示矩形 $i$ 的左下角坐标，$(bx_i,by_i)$ 表示矩形 $i$ 的右上角坐标。

首先我们可以很快列出一个式子，如果矩形 $j$ 覆盖矩形 $i$ 当且仅当

$i < j$。
$bx_i \ge ax_j,ax_i \le bx_j$（横坐标有交）。
$by_i \ge ay_j,ay_i \le by_j$（纵坐标有交）。

如果直接求这个式子会发现这是一个五维偏序，最优时间复杂度是 $O(n\log^4n)$ 的 cdq 分治嵌套或 $O(n^{\frac{9}{5}})$ 的 KD Tree。这都无法通过。但是这题求的不是方案数，而是是否存在，这就有一点希望。

我们考虑按照传统 cdq 分治的思路来处理，先按照编号分治处理，然后左边按照 $bx_i$ 排序，右边按照 $ax_j$ 排序，双指针处理。现在我们考虑剩下三维怎么处理？

我们发现如果按照纵坐标考虑的话就是矩形 $i$ 和矩形 $j$ 的纵坐标部分有交点。此时只要再满足存在 $bx_j \ge ax_i$ 即可。

我们考虑要判断是否存在，可以求 $bx_j$ 的最大值。而纵坐标部分有交，我们可以以纵坐标建立线段树，实现区间赋最大值，区间查询最大值。这样子的线段树是 $O(n\log n)$ 的，总时间是 $O(n\log^2n)$ 的，可以通过。

而清空的时候，我们不能真的清空，可以实现一个清空的懒标记，和赋值的懒标记一起下传。

记得离散化。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 200005
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n, ax[N], ay[N], bx[N], by[N], id[N], ans[N], nls[N], cnt;
il bool cmp1(int i, int j){return bx[i] < bx[j];}
il bool cmp2(int i, int j){return ax[i] < ax[j];}
int tr[N << 2], tag[N << 2], clr[N << 2];
il void pd(int p){
    if (clr[p]) clr[p << 1] = clr[p << 1 | 1] = 1, tr[p << 1] = tr[p << 1 | 1] = tag[p << 1] = tag[p << 1 | 1] = 0;
    if (tag[p]) tr[p << 1] = max(tr[p << 1], tag[p]), tr[p << 1 | 1] = max(tr[p << 1 | 1], tag[p]), tag[p << 1] = max(tag[p << 1], tag[p]), tag[p << 1 | 1] = max(tag[p << 1 | 1], tag[p]);
    clr[p] = tag[p] = 0;
}
void upd(int p, int l, int r, int nl, int nr, int k){
    if (nl <= l && r <= nr) return tr[p] = max(tr[p], k), tag[p] = max(tag[p], k), void(0);
    int mid = (l + r) >> 1;
    pd(p);
    if (nl <= mid) upd(p << 1, l, mid, nl, nr, k); if (nr > mid) upd(p << 1 | 1, mid + 1, r, nl, nr, k);
    tr[p] = max(tr[p << 1], tr[p << 1 | 1]);
}
int qry(int p, int l, int r, int nl, int nr){
    if (nl <= l && r <= nr) return tr[p];
    int mid = (l + r) >> 1, ans = 0;
    pd(p);
    if (nl <= mid) ans = max(ans, qry(p << 1, l, mid, nl, nr)); if (nr > mid) ans = max(ans, qry(p << 1 | 1, mid + 1, r, nl, nr));
    return ans;
}
void cdq(int l, int r){
    if (l == r) return ;
    int mid = (l + r) >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    sort (id + l, id + mid + 1, cmp1), sort (id + mid + 1, id + r + 1, cmp2);
    for (int i = l, j = mid + 1; i <= mid; i++){
        for (; j <= r && ax[id[j]] <= bx[id[i]]; j++) upd(1, 1, n + n, ay[id[j]], by[id[j]], bx[id[j]]);
        int t = qry(1, 1, n + n, ay[id[i]], by[id[i]]);
        ans[id[i]] |= (t >= ax[id[i]]);
    }
    clr[1] = 1, tr[1] = tag[1] = 0;
}
signed main(){
    n = rd();
    for (int i = 1; i <= n; i++) ax[i] = rd(), ay[i] = rd(), bx[i] = ax[i] + rd() - 1, by[i] = ay[i] + rd() - 1, id[i] = i;
    for (int i = 1; i <= n; i++) nls[i] = ax[i], nls[n + i] = bx[i];
    sort (nls + 1, nls + n + n + 1), cnt = unique(nls + 1, nls + n + n + 1) - nls - 1;
    for (int i = 1; i <= n; i++) ax[i] = lower_bound(nls + 1, nls + cnt + 1, ax[i]) - nls, bx[i] = lower_bound(nls + 1, nls + cnt + 1, bx[i]) - nls;
    for (int i = 1; i <= n; i++) nls[i] = ay[i], nls[n + i] = by[i];
    sort (nls + 1, nls + n + n + 1), cnt = unique(nls + 1, nls + n + n + 1) - nls - 1;
    for (int i = 1; i <= n; i++) ay[i] = lower_bound(nls + 1, nls + cnt + 1, ay[i]) - nls, by[i] = lower_bound(nls + 1, nls + cnt + 1, by[i]) - nls;
    cdq(1, n);
    for (int i = 1; i <= n; i++) puts(ans[i] ? "NE" : "DA");
    return 0;
}

Grass Segments G

给定 $n$ 条线段，对于每一条线段 $i$，求与它相交部分长度至少为 $k_i$ 的线段数量。

猜你想搜：NOIP 2024 T4。

这题实际上是 NOIP 2024 T4 的一部分，可惜我赛前没有做这题，现在才做。

cdq 分治

我们直接考虑刻画相交部分长度，实际上就是 $\min(r_i,r_j) - \max(l_i,l_j) \ge k_i$，注意这里的长度不用 $+1$。

我们可以转化成下面的形式。

$$k_i \le \min\{r_i-l_i,r_i-l_j,r_j-l_i,r_j-l_j\}$$

然后展开可以得到

$$ \left\{\begin{matrix} k_i \le r_i - l_i\\ k_i \le r_i - l_j\\ k_i \le r_j - l_i\\ k_i \le r_j - l_j \end{matrix}\right. $$

题目保证了 $k_i \le r_i - l_i$，现在我们只要满足后面 $3$ 个条件，转化一下。

$$ \left\{\begin{matrix} r_i - k_i \ge l_j\\ l_i + k_i \le r_j\\ k_i \le r_j - l_j \end{matrix}\right. $$

这是一个三位偏序的形式，我们可以 cdq 分治。但是这题最大的问题在于我们没有一个比较好的第一层排序方法。在以往的 cdq 分治求三位偏序的题目中，我们可以根据 $a_i \le a_j$ 这样的条件，按照 $a$ 来排序，但是这题没有这样一个条件，我们无法排序。

这时候我们可以构造出来 $a_i \le a_j$ 的形式。具体的，我们复制一下这个序列，然后令新的序列中的 $k_i$ 变成 $r_i-l_i$，此时我们发现就有 $k_i \le k_j$ 的限制了。此时我们可以排序，直接 cdq 分治即可。

注意，这时候只有新的序列才会产生贡献，旧的是没有的。如果 $k_i$ 相同，我们要把新序列排在后面（实际上前面也可以，主要看 cdq 分治内部怎么实现）。

要离散化。时间复杂度 $O(n\log^2n)$。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 1000005
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n, m, id[N], l[N], r[N], k[N], x[N], y[N], ans[N], tr[N], nls[N], cnt;
il bool cmpk(int i, int j){return k[i] != k[j] ? k[i] < k[j] : i < j;}
il bool cmp1(int i, int j){return x[i] != x[j] ? x[i] > x[j] : i < j;}
il bool cmp2(int i, int j){return r[i] != r[j] ? r[i] > r[j] : i < j;}
il void add(int x, int k){for (int i = x; i <= n; i += (i & (-i))) tr[i] += k;}
il int ask(int x){int ans = 0;for (int i = x; i >= 1; i -= (i & (-i))) ans += tr[i];return ans;}
il void clr(int x){for (int i = x; i <= n; i += (i & (-i))) tr[i] = 0;}
void cdq(int L, int R){
    if (L == R) return ;
    int Mid = (L + R) >> 1;
    cdq(L, Mid), cdq(Mid + 1, R);
    sort (id + L, id + Mid + 1, cmp1), sort (id + Mid + 1, id + R + 1, cmp2);
    for (int i = L, j = Mid + 1; i <= Mid; i++){
        for (; j <= R && r[id[j]] >= x[id[i]]; j++) if (id[j] > m) add(l[id[j]], 1);
        if (id[i] <= m) ans[id[i]] += ask(y[id[i]]);
    }
    for (int i = Mid + 1; i <= R; i++) clr(l[id[i]]);
}
signed main(){
    m = rd();
    for (int i = 1; i <= m; i++) l[i] = rd(), r[i] = rd(), k[i] = rd(), id[i] = i;
    for (int i = m + 1; i <= m + m; i++) l[i] = l[i - m], r[i] = r[i - m], k[i] = r[i] - l[i], id[i] = i;
    n = m + m;
    sort (id + 1, id + n + 1, cmpk);
    for (int i = 1; i <= n; i++) x[i] = l[i] + k[i], y[i] = r[i] - k[i], nls[++cnt] = l[i], nls[++cnt] = y[i];
    sort (nls + 1, nls + cnt + 1), cnt = unique(nls + 1, nls + cnt + 1) - nls - 1;
    for (int i = 1; i <= n; i++) l[i] = lower_bound(nls + 1, nls + cnt + 1, l[i]) - nls, y[i] = lower_bound(nls + 1, nls + cnt + 1, y[i]) - nls;
    cdq(1, n);
    for (int i = 1; i <= m; i++) printf ("%d\n", ans[i] - 1);
    return 0;
}

离线二维数点/扫描线

我们换一种刻画区间交的方法。考虑 $r_j$ 是否在区间 $[l_i,r_i]$ 内。

$$ \left\{\begin{matrix} r_j \ge r_i,l_j \le r_i-k_i\\ r_j \in [l_i+k_i,r_i],r_j-l_j\ge k_i \end{matrix}\right. $$

这两种实际上都是合法的，我们分别统计。注意到每一个实际上都是一个二维偏序的形式，可以直接扫描线，不用 cdq 分治。时间复杂度 $O(n\log n)$，同样要离散化。

代码就不贴了，如果用动态开点应该不用离散化。

镜中的昆虫

给定序列 $a$，要支持区间推平，区间查询颜色种类数。

~~让我们赞美 $64$ MB 的空间。~~

不带修

不带修就是经典的区间数颜色，我们考虑记每一个位置前一个与其相同的颜色的位置。然后我们只需要记录最左边的颜色个数即可。这时候就是要满足 $pre_i < l, i \in [l,r]$。这个可以直接扫描线即可。主席树在这个空间下过不了。

单点修

我们考虑一次修改，只会影响到至多三个位置的 $pre$，我们暴力修改 $pre$，然后可以用树状数组套主席树，但是空间不够，我们离线下来。

考虑记录每个位置每个时候 $pre$ 的信息，分别为位置 $i$，前驱 $pre$ 以及时间 $time$。此时我们发现这就是三位偏序，可以直接 cdq 分治做到 $O(n\log^2n)$。

至于求出哪些位置的 $pre$ 发生变化，可以每个颜色都开一个 set。

区间修

这时候我们似乎没有什么比较好的方法，看上去 $pre$ 的变化量会直接爆到 $O(nm)$。但是如果你尝试去卡的话，你会发现根本卡不掉。此时我们考虑能否证明 $pre$ 变换量。

结论：$m$ 次区间推平后 $pre$ 的变化量是 $O(n + m)$ 的。

考虑 ODT，我们在区间推平的时候，会在 ODT 上分裂两边的点，然后删除中间若干个点，添加至多三个点。每个节点至多被删除一次，并且要使得 $pre$ 变化，只有加入和删除的时候有贡献，所以最多只有 $O(n+m)$ 次变化。

既然如此，那我们是不是就可以暴力找到这些 $pre$ 变化的点，然后用单点修改的 cdq 分治。

至于怎么找到这些点，我们就用 ODT 来实现。这里我们要给每一个颜色开一个 ODT。

#include <bits/stdc++.h>
using namespace std;
#define il inline
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
struct Point{
    int x, y, t, val, id;
}p[1500005];
int cnt, pre[200005], lst[200005], n, m, a[100005], mcnt, ans_cnt, ans[100005];
unordered_map <int, int> mp;
struct Node{
    int l, r;
    mutable int v;
    Node(int l, int r = 0, int v = 0) : l(l), r(r), v(v){}
    bool operator <(const Node &a) const{return l < a.l;}
};
struct ODT{
    #define iter set<Node>::iterator
    set <Node> tr, col[200005];
    iter Insert(int l, int r, int v){
        col[v].insert(Node(l, r, v));
        return tr.insert(Node(l, r, v)).first;
    }
    void Delete(int l, int r, int v){
        col[v].erase(Node(l, r, v));
        tr.erase(Node(l, r, v));
    }
    iter split(int pos){
        iter it = tr.lower_bound(Node(pos));
        if (it != tr.end() && it->l == pos) return it;
        it--;
        if (it->r < pos) return tr.end();
        int l = it->l, r = it->r, v = it->v;
        Delete(l, r, v), Insert(l, pos - 1, v);
        return Insert(pos, r, v);
    }
    int Pre(int pos){
        iter it = --tr.upper_bound(Node(pos));
        if (it->l < pos) return pos - 1;
        iter c = col[it->v].lower_bound(Node(pos));
        if (c != col[it->v].begin()) return (--c)->r;
        return 0;
    }
    void assign (int l, int r, int v, int t){
        iter itr = split(r + 1), itl = split(l);
        vector <int> ps;
        for (iter it = itl; it != itr; it++){
            if (it != itl) ps.push_back(it->l);
            iter nxt = col[it->v].upper_bound(*it);
            if (nxt != col[it->v].end()) ps.push_back(nxt->l);
            col[it->v].erase(*it);
        }
        tr.erase(itl, itr), Insert(l, r, v), ps.push_back(l);
        iter nxt = col[v].upper_bound(Node(l, r, v));
        if (nxt != col[v].end()) ps.push_back(nxt->l);
        for (int i = 0; i < ps.size(); i++){
            p[++cnt] = Point{ps[i], pre[ps[i]], t, -1, 0};
            pre[ps[i]] = Pre(ps[i]);
            p[++cnt] = Point{ps[i], pre[ps[i]], t, 1, 0};
        }
    }
}odt;

il bool cmp1(const Point &a, const Point &b){return a.t != b.t ? a.t < b.t : a.id < b.id;}
il bool cmp2(const Point &a, const Point &b){return a.x != b.x ? a.x < b.x : a.id < b.id;}
struct BIT{
    int tr[100005];
    il void add(int x, int k){for (int i = x; i <= 100000; i += (i & (-i))) tr[i] += k;}
    il int ask(int x){int ans = 0;for (int i = x; i >= 1; i -= (i & (-i))) ans += tr[i];return ans;}
}bit;
void cdq(int l, int r){
    if (l == r) return ;
    int mid = (l + r) >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    int i, j;
    for (i = l, j = mid + 1; j <= r; j++){
        for (; i <= mid && p[i].x <= p[j].x; i++) if (!p[i].id) bit.add(p[i].y + 1, p[i].val);
        if (p[j].id) ans[p[j].id] += bit.ask(p[j].y + 1) * p[j].val;
    }
    for (int k = l; k < i; k++) if (!p[k].id) bit.add(p[k].y + 1, -p[k].val);
    inplace_merge(p + l, p + mid + 1, p + r + 1, cmp2);
} 
signed main(){
    n = rd(), m = rd();
    for (int i = 1; i <= n; i++){
        a[i] = rd();
        if (!mp[a[i]]) mp[a[i]] = ++mcnt;
        a[i] = mp[a[i]], pre[i] = lst[a[i]], lst[a[i]] = i;
        p[++cnt] = Point{i, pre[i], 0, 1, 0};
        odt.Insert(i, i, a[i]);
    }
    for (int i = 1, op, l, r, v; i <= m; i++){
        op = rd();
        if (op == 1){
            l = rd(), r = rd(), v = rd();
            if (!mp[v]) mp[v] = ++mcnt;
            v = mp[v], odt.assign(l, r, v, i); 
        }
        else{
            l = rd(), r = rd(), ans_cnt++;
            p[++cnt] = Point{r, l - 1, i, 1, ans_cnt};
            p[++cnt] = Point{l - 1, l - 1, i, -1, ans_cnt};
        }
    }
    sort (p + 1, p + cnt + 1, cmp1);
    cdq(1, cnt);
    for (int i = 1; i <= ans_cnt; i++) printf ("%d\n", ans[i]);
    return 0;
}

2.cdq 分治优化 dp

我们先来讲一下 cdq 分治优化 dp 的通用公式。

递归处理 $[l,mid]$ 区间，求出 dp 值。
将 $[l,mid]$ 的值转移到 $[mid+1,r]$ 上。
递归求解 $[mid+1,r]$ 的 dp 值。

主要的问题就在于如何转移。这里转移最大的优点在于转移的出发点是固定的，我们不需要动态得到一些值，可以先预处理，然后求解。简单来讲，就是修改操作和查询操作完全分离。

这样子，我们可以避免一些不必要的动态操作。

拦截导弹

~~不会有人看成导弹拦截了吧？~~

求二维的最长不下降子序列长度以及每个点称为该子序列上一个点的概率。

我们容易想到一个 dp。定义 $f_i$ 表示以 $i$ 结尾的二维最长不上升子序列（后文称为 LDS）的长度。我们就可以设计出 $O(n^2)$ 的转移。

$$f_i = \max_{j<i,a_j \ge a_i,b_j \ge b_i} f_j + 1$$

然后求每个点的概率。容易想到要求经过每个点的 LDS 个数。于是我们定义 $g_i$ 表示以 $i$ 结尾的 LDS 个数。然后我们同样可以容易得到 $O(n^2)$ 的转移。

$$g_i = \sum_{j<i,a_j \ge a_i,b_j \ge b_i} [f_j + 1 = f_i]g_j$$

但是这只是以 $i$ 结尾的答案，我们要的是经过 $i$ 的答案，于是我们要再求一个以 $i$ 为开头的 LDS 长度及个数。

为了区分，定义以 $i$ 为结尾的 LDS 是 $f1_i,g1_i$，以 $i$ 为开头的 LDS 是 $f2_i,g2_i$。二者转移是类似的。

首先可以求出 LDS 的长度，及 $f1_i$ 的最大值，设为 $maxn$。

现在求概率，我们要先求出总的方案数，设为 $sum$。

$$sum = \sum_{i=1}^n [f1_i = maxn]g1_i$$

然后我们判断一个点的方案数，就是 $g1_i \times g2_i$。但是前提是 $f1_i + f2_i - 1 = maxn$，及经过 $i$ 的 LDS 长度是 $maxn$。概率就是 $\frac{g1_i \times g2_i}{sum}$。

int n, maxn, f1[N], f2[N];
double sum, g1[N], g2[N];
struct Point{
    int h, w;   
}p[N];
signed main(){
    n = rd();
    for (int i = 1; i <= n; i++) p[i] = Point{rd(), rd()};
    for (int i = 1; i <= n; i++){
        f1[i] = 1;
        for (int j = 1; j < i; j++) if (p[j].h >= p[i].h && p[j].w >= p[i].w) f1[i] = max(f1[i], f1[j] + 1);
        for (int j = 1; j < i; j++) if (p[j].h >= p[i].h && p[j].w >= p[i].w && f1[j] + 1 == f1[i]) g1[i] += g1[j];
        if (!g1[i]) g1[i]++;
    }
    for (int i = n; i >= 1; i--){
        f2[i] = 1;
        for (int j = i + 1; j <= n; j++) if (p[j].h <= p[i].h && p[j].w <= p[i].w) f2[i] = max(f2[i], f2[j] + 1);
        for (int j = i + 1; j <= n; j++) if (p[j].h <= p[i].h && p[j].w <= p[i].w && f2[j] + 1 == f2[i]) g2[i] += g2[j];
        if (!g2[i]) g2[i]++;
    }
    for (int i = 1; i <= n; i++) maxn = max(maxn, f1[i]);
    printf ("%lld\n", maxn);
    for (int i = 1; i <= n; i++) if (f1[i] == maxn) sum += g1[i];
    for (int i = 1; i <= n; i++) if (f1[i] + f2[i] - 1 == maxn) printf ("%.5lf ", g1[i] * g2[i] / sum); else printf ("0.00000 ");
    return 0;
}

然后 T 飞了。这个时间复杂度是 $O(n^2)$ 的。我们考虑优化。

考虑一维的时候我们可以用二分或线段树维护来做到单点加，区间最大值。这样子就是 $O(n\log n)$ 的。但是现在是二维的，难道我们用二维线段树？

~~确实可以，但是你想写吗？~~

我们用 cdq 分治，可以做到时间 $O(n\log^2n)$，空间 $O(n)$。实际上，这是一道 cdq 优化 dp 的板子。

套路的，我们要分治解决这个问题。以 $f1_i$ 和 $g1_i$ 为例。设当前区间是 $[l,r]$，中点是 $mid$。

求区间 $[l,mid]$ 的 dp 值。
将 $[l,mid]$ 的 dp 值转移给 $[mid+1,r]$ 的 dp 值。
求 $[mid+1,r]$ 的 dp 值。

第 $1$ 步和第 $3$ 步都是递归求解，主要是第 $2$ 步。

考虑转移的限制有三个，为 $j<i,a_j \ge a_i,b_j \ge b_i$。其中我们用分治处理了第一个限制，然后我们暴力按照 $a$ 排序，双指针处理解决掉第 $2$ 个限制。现在只剩第 $3$ 个限制。我们可以直接用线段树单点修改区间查询解决。

首先考虑线段树中维护最大的 $f$ 以及这些位置对应的 $g$ 的和。用一个结构体封装起来，如下代码。

struct Tree{
    int mx;double ct;
}tr[N << 2];
Tree operator +(const Tree &a, const Tree &b){
    if (a.mx > b.mx) return a;
    if (a.mx < b.mx) return b;
    return Tree{a.mx, a.ct + b.ct};
}
void clr(int p, int l, int r){
    if (!tr[p].mx) return ;// 这一句很关键，否则时间复杂度会退化到 O(n^2log n)
    tr[p] = Tree{0, 0};
    if (l == r) return ;
    int mid = (l + r) >> 1;
    clr(p << 1, l, mid), clr(p << 1 | 1, mid + 1, r);
}
void upd(int p, int l, int r, int x, Tree k){
    if (l == r) return tr[p] = tr[p] + k, void(0);
    int mid = (l + r) >> 1;
    if (x <= mid) upd(p << 1, l, mid, x, k);
    else upd(p << 1 | 1, mid + 1, r, x, k);
    tr[p] = tr[p << 1] + tr[p << 1 | 1];
}
Tree qry(int p, int l, int r, int nl, int nr){
    if (nl <= l && r <= nr) return tr[p];
    int mid = (l + r) >> 1;
    if (nl <= mid && mid < nr) return qry(p << 1, l, mid, nl, nr) + qry(p << 1 | 1, mid + 1, r, nl, nr);
    if (nl <= mid) return qry(p << 1, l, mid, nl, nr);
    return qry(p << 1 | 1, mid + 1, r, nl, nr);
}

这里 $mx$ 就是最大的 $f$，$ct$ 就是个数。

看一下主要的 cdq 分治代码。

struct Point{
    int id, h, w;
}p[N];
bool operator <(const Point &a, const Point &b){return a.id < b.id;}
il bool cmp(Point a, Point b){return (a.h != b.h) ? (a.h > b.h) : (a.id < b.id);}
void cdq1(int l, int r){
    if (l == r) return ;
    sort (p + l, p + r + 1);// 按照编号排序
    int mid = (l + r) >> 1;
    cdq1(l, mid);
    sort (p + l, p + mid + 1, cmp), sort(p + mid + 1, p + r + 1, cmp);// 按照第一维排序
    clr(1, 1, n);// 清空线段树
    for (int i = l, j = mid + 1; j <= r; j++){// 双指针
        for (; i <= mid && p[i].h >= p[j].h; i++) upd(1, 1, n, p[i].w, f[p[i].id]);
        Tree t = qry(1, 1, n, p[j].w, n);
        t.mx++;
        f[p[j].id] = f[p[j].id] + t;// 转移
    }
    cdq1(mid + 1, r);
}

这个过程很简单，只要理解了上面所说的应该都不难。

完整代码。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
#define N 100005
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n, nls[N], cnt, maxn;
double sum;
struct Point{
    int id, h, w;
}p[N];
bool operator <(const Point &a, const Point &b){return a.id < b.id;}
il bool cmp(Point a, Point b){return (a.h != b.h) ? (a.h > b.h) : (a.id < b.id);}
struct Tree{
    int mx;double ct;
}tr[N << 2], f[N], g[N];
Tree operator +(const Tree &a, const Tree &b){
    if (a.mx > b.mx) return a;
    if (a.mx < b.mx) return b;
    return Tree{a.mx, a.ct + b.ct};
}
void clr(int p, int l, int r){
    if (!tr[p].mx) return ;
    tr[p] = Tree{0, 0};
    if (l == r) return ;
    int mid = (l + r) >> 1;
    clr(p << 1, l, mid), clr(p << 1 | 1, mid + 1, r);
}
void upd(int p, int l, int r, int x, Tree k){
    if (l == r) return tr[p] = tr[p] + k, void(0);
    int mid = (l + r) >> 1;
    if (x <= mid) upd(p << 1, l, mid, x, k);
    else upd(p << 1 | 1, mid + 1, r, x, k);
    tr[p] = tr[p << 1] + tr[p << 1 | 1];
}
Tree qry(int p, int l, int r, int nl, int nr){
    if (nl <= l && r <= nr) return tr[p];
    int mid = (l + r) >> 1;
    if (nl <= mid && mid < nr) return qry(p << 1, l, mid, nl, nr) + qry(p << 1 | 1, mid + 1, r, nl, nr);
    if (nl <= mid) return qry(p << 1, l, mid, nl, nr);
    return qry(p << 1 | 1, mid + 1, r, nl, nr);
}
void cdq1(int l, int r){
    if (l == r) return ;
    sort (p + l, p + r + 1);
    int mid = (l + r) >> 1;
    cdq1(l, mid);
    sort (p + l, p + mid + 1, cmp), sort(p + mid + 1, p + r + 1, cmp);
    clr(1, 1, n);
    for (int i = l, j = mid + 1; j <= r; j++){
        for (; i <= mid && p[i].h >= p[j].h; i++) upd(1, 1, n, p[i].w, f[p[i].id]);
        Tree t = qry(1, 1, n, p[j].w, n);
        t.mx++;
        f[p[j].id] = f[p[j].id] + t;
    }
    cdq1(mid + 1, r);
}
void cdq2(int l, int r){
    if (l == r) return ;
    sort (p + l, p + r + 1);
    int mid = (l + r) >> 1;
    cdq2(mid + 1, r);
    sort (p + l, p + mid + 1, cmp), sort(p + mid + 1, p + r + 1, cmp);
    clr(1, 1, n);
    for (int i = mid, j = r; i >= l; i--){
        for (; j > mid && p[j].h <= p[i].h; j--) upd(1, 1, n, p[j].w, g[p[j].id]);
        Tree t = qry(1, 1, n, 1, p[i].w);
        t.mx++;
        g[p[i].id] = g[p[i].id] + t;
    }
    cdq2(l, mid);
}
signed main(){
    n = rd();
    for (int i = 1; i <= n; i++) p[i] = Point{i, rd(), rd()}, nls[i] = p[i].w, f[i] = g[i] = Tree{1, 1};
    sort (nls + 1, nls + n + 1);
    cnt = unique(nls + 1, nls + n + 1) - nls - 1;
    for (int i = 1; i <= n; i++) p[i].w = lower_bound(nls + 1, nls + cnt + 1, p[i].w) - nls;
    cdq1(1, n), cdq2(1, n);
    for (int i = 1; i <= n; i++) maxn = max(maxn, f[i].mx);
    printf ("%lld\n", maxn);
    for (int i = 1; i <= n; i++) if (f[i].mx == maxn) sum += f[i].ct;
    for (int i = 1; i <= n; i++) if (f[i].mx + g[i].mx - 1 == maxn) printf ("%.5lf ", f[i].ct * g[i].ct / sum); else printf ("0.00000 ");
    return 0;
}

[CH弱省胡策R2] TATT

求四维最长不下降子序列长度。

~~简易的题目，暴力的算法。~~

我们按照上一题的思路来做，用 cdq 分治实现，但是我们发现最后只用树状数组似乎不够了，因为我们还剩下两维。此时我们有一个暴力的想法：既然还剩两维，那么直接树套树吧。

~~然后就过了。~~时间复杂度 $O(n\log^3n)$。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 100005
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n, f[N], nls[N], cnt, maxn;
struct Point{
    int a, b, c, d, id;
}p[N];
il bool cmp1(Point x, Point y){return x.a != y.a ? x.a < y.a : x.b != y.b ? x.b < y.b : x.c != y.c ? x.c < y.c : x.d != y.d ? x.d < y.d : x.id < y.id;}
il bool cmp2(Point x, Point y){return x.b != y.b ? x.b < y.b : x.a != y.a ? x.a < y.a : x.c != y.c ? x.c < y.c : x.d != y.d ? x.d < y.d : x.id < y.id;}
int rt[N], tr[N << 6], ls[N << 6], rs[N << 6], ep;
void upd(int &p, int l, int r, int x, int k){
    if (!p) p = ++ep, tr[p] = ls[p] = rs[p] = 0;
    if (l == r) return tr[p] = max(tr[p], k), void(0);
    int mid = (l + r) >> 1;
    if (x <= mid) upd(ls[p], l, mid, x, k); else upd(rs[p], mid + 1, r, x, k);
    tr[p] = max(tr[ls[p]], tr[rs[p]]);
}
int qry(int p, int l, int r, int nl, int nr){
    if (!p) return 0;
    if (nl <= l && r <= nr) return tr[p];
    int mid = (l + r) >> 1, ans = 0;
    if (nl <= mid) ans = max(ans, qry(ls[p], l, mid, nl, nr)); if (nr > mid) ans = max(ans, qry(rs[p], mid + 1, r, nl, nr));
    return ans;
}
il void add(int x, int y, int k){for (int i = x; i <= n; i += (i & (-i))) upd(rt[i], 1, n, y, k);}
il int ask(int x, int y){int ans = 0;for (int i = x; i >= 1; i -= (i & (-i))) ans = max(ans, qry(rt[i], 1, n, 1, y));return ans;}
il void clr(int x){for (int i = x; i <= n; i += (i & (-i))) rt[i] = 0;}
void cdq(int l, int r){
    if (l == r) return ;
    sort (p + l, p + r + 1, cmp1);
    int mid = (l + r) >> 1;
    cdq(l, mid);
    sort (p + l, p + mid + 1, cmp2), sort (p + mid + 1, p + r + 1, cmp2);
    for (int i = l, j = mid + 1; j <= r; j++){
        for (; i <= mid && p[i].b <= p[j].b; i++) add(p[i].c, p[i].d, f[p[i].id]);
        f[p[j].id] = max(f[p[j].id], ask(p[j].c, p[j].d) + 1);
    }
    for (int i = l; i <= mid; i++) clr(p[i].c);
    ep = 0;
    cdq(mid + 1, r);
}
signed main(){
    n = rd();
    for (int i = 1; i <= n; i++) p[i] = Point{rd(), rd(), rd(), rd(), i}, f[i] = 1;
    for (int i = 1; i <= n; i++) nls[i] = p[i].a;sort (nls + 1, nls + n + 1), cnt = unique(nls + 1, nls + n + 1) - nls - 1;
    for (int i = 1; i <= n; i++) p[i].a = lower_bound(nls + 1, nls + cnt + 1, p[i].a) - nls;
    for (int i = 1; i <= n; i++) nls[i] = p[i].b;sort (nls + 1, nls + n + 1), cnt = unique(nls + 1, nls + n + 1) - nls - 1;
    for (int i = 1; i <= n; i++) p[i].b = lower_bound(nls + 1, nls + cnt + 1, p[i].b) - nls;
    for (int i = 1; i <= n; i++) nls[i] = p[i].c;sort (nls + 1, nls + n + 1), cnt = unique(nls + 1, nls + n + 1) - nls - 1;
    for (int i = 1; i <= n; i++) p[i].c = lower_bound(nls + 1, nls + cnt + 1, p[i].c) - nls;
    for (int i = 1; i <= n; i++) nls[i] = p[i].d;sort (nls + 1, nls + n + 1), cnt = unique(nls + 1, nls + n + 1) - nls - 1;
    for (int i = 1; i <= n; i++) p[i].d = lower_bound(nls + 1, nls + cnt + 1, p[i].d) - nls;
    cdq(1, n);
    for (int i = 1; i <= n; i++) maxn = max(maxn, f[i]);
    printf ("%d\n", maxn);
    return 0;
}

附赠三倍经验：德丽莎世界第一可爱，寻找宝藏。

序列

给定序列 $a$，有 $m$ 次修改，每次将 $a_x$ 改为 $k$。每个修改之间互不影响。求最长的子序列，满足在任意的修改版本中（包括初始版本）都是单调不降的。

由于是单点求改，互不影响，所以考虑一对位置 $(i,j),i<j$ 同时选的条件。我们假设第 $k$ 次修改修改了 $a_{x_k}$，变成了 $t_k$。

$\forall x_k = i,t_k \le a_j$。
$\forall x_k = j,a_i \le t_k$。
$a_i \le a_j$。

我们可以容易的发现只要求出每个位置修改之后的最小最大值即可判断。假设位置 $i$ 修改后的最小最大值分别是 $mn_i,mx_i$，那么就有

$mx_i \le a_j$。
$a_i \le mn_j$。
$i < j$。

这是一个三位偏序，直接 cdq 分治优化 dp 即可。

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define N 100005
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n, m, a[N], mx[N], mn[N], f[N], tr[N], maxn, id[N];
il bool cmp1(int x, int y){return mx[x] < mx[y];}
il bool cmp2(int x, int y){return a[x] < a[y];}
il void clr(int x){for (int i = x; i <= N - 5; i += (i & (-i))) tr[i] = 0;}
il void add(int x, int k){for (int i = x; i <= N - 5; i += (i & (-i))) tr[i] = max(tr[i], k);}
il int ask(int x){int ans = 0;for (int i = x; i >= 1; i -= (i & (-i))) ans = max(ans, tr[i]);return ans;}
void cdq(int l, int r){
    if (l == r) return ;
    sort (id + l, id + r + 1);
    int mid = (l + r) >> 1;
    cdq(l, mid), sort (id + l, id + mid + 1, cmp1), sort(id + mid + 1, id + r + 1, cmp2);
    for (int i = l, j = mid + 1; j <= r; j++){
        for (; i <= mid && mx[id[i]] <= a[id[j]]; i++) add(a[id[i]], f[id[i]]);
        f[id[j]] = max(f[id[j]], ask(mn[id[j]]) + 1);
    }
    for (int i = l; i <= mid; i++) clr(a[id[i]]);
    cdq(mid + 1, r);
}
signed main(){
    n = rd(), m = rd();
    for (int i = 1; i <= n; i++) mx[i] = mn[i] = a[i] = rd(), id[i] = i, f[i] = 1;
    for (int i = 1, x, k; i <= m; i++) x = rd(), k = rd(), mx[x] = max(mx[x], k), mn[x] = min(mn[x], k);
    cdq(1, n);
    for (int i = 1; i <= n; i++) maxn = max(maxn, f[i]);
    printf ("%d\n", maxn);
    return 0;
}

后记

实际上 cdq 分治可以配合斜率优化的题目，但是已经有李超线段树了，所以就没有写了。

关于多项式的话，会有分治 FFT，本质上就是 cdq 分治优化 dp，只是中间 dp 的过程用的是 FFT 罢了。

3 评论

Conan15 2025-06-13 15:57 · 福建

分治 FFT/NTT 本质上不算 CDQ 吧，只是普通分治思想套了一个已知算法。

Conan15 2025-06-13 15:58 · 福建

嗯你的意思可能是分治 FFT/NTT 优化 DP……那个确实是 CDQ

Union_Find 2025-06-13 16:17 · 福建

可能没解释清楚吧，有一类特殊的分治 FFT 是类似于 cdq 优化 dp 的，比如分治 FFT 板子

App 内打开