暑期专题四 CDQ分治
前置知识:归并排序 + 树状数组/线段树
CDQ分治其实是一种思想,即在解决偏序问题时归并排序,并整体考虑前一半对后一半的贡献,但是它很多时候可以用来替换一层树,所以一般把它算作数据结构(?)
例如求逆序对,我们归并排序其实就用到了CDQ分治的思想。具体怎么运用到的呢?这个题实际上是一个二维偏序,即设在原数列中的第\(i\)个数的编号为\(a_i\),数值为\(b_i\),求所有数字对,满足\(b_j > b_i\)且\(a_j < a_i\)。我们当时是怎么求它的逆序对的呢?一开始的时候\(a_i\)显然有序,那么递归地处理,先处理前一半并按\(b_i\)排序,后一半同理,然后这个时候,对于前一半已排序的数列来说,它们的\(a_i\)无序,对于后一半已排序的数列来说,它们的\(a_i\)同样无序,但是有一个性质,即前一半的任何一个元素的\(a_i\)一定小于后一半的任何一个元素的\(a_i\)!!!有了这样一个性质,且前一半和后一半分别对\(b_i\)有序,那么对于前一半中的元素\(i\)和后一半中的元素\(j\)来说,如果\(b_j < b_i\),那么\(i\)到\(mid\)这一段的元素,都必然满足逆序对的条件,这样我们就可以计算出贡献了。
另,CDQ分治有两种写法,第一种是在CDQ分治计算贡献的时候顺带用辅助数组归并排序,好处常数小,坏处码量较大,稍显繁琐且空间较大;第二种是CDQ分治先归并处理前一半和后一半后,直接用STL自带的sort排序,好处码量小,思路简洁且空间小,坏处常数大,卡常题卡不过去。
一、二维偏序
1.NKOJ1321 数列操作
题意概述:板题,有一个数列\(n\)个数,要求支持单点修改,区间查询(总和)。
思路:这个题已经我们已经学了好几种简单的方法可以来解决,包括树状数组,线段树甚至分块。但是今天我们尝试用CDQ分治来解决这道题。首先利用前缀和,将区间\(s\)到\(t\)求和转化为\(sum[t] - sum[s - 1]\),这样就变成了两个独立的操作。然后将\(n\)个数的初始值想象成\(n\)次ADD,然后总共就有\(n+m\)次操作(即修改+查询)。然后用CDQ分治,将操作时间看成第一维,操作位置看成第二维,考虑前一半对后一半的贡献,前一半的任何一个的操作时间显然都小于后一半的任何一个的操作时间,所以设有前一半中的\(i\)(为修改)和后一半中的\(j\)(为查询),如果\(i\)修改的位置小于等于\(j\)查询的位置,那么\(l\)到\(i\)的修改显然都会对\(j\)的查询产生贡献。
以下是两种CDQ分治写法的优劣对比:
第一种:
#include
using namespace std;
const int N = 5e5 + 5;
struct node {
int tp, x, y;
}a[N], tmp[N];
int ans[N], pre[N];
void CDQ(int l, int r)
{
if (l == r) return;
int mid = l + r >> 1, i = l, j = mid + 1, k = 1, sum = 0;
CDQ(l, mid), CDQ(mid + 1, r);
while (i <= mid && j <= r)
{
if (a[i].x <= a[j].x)
{
if (!a[i].tp) sum += a[i].y;
tmp[k++] = a[i++];
}
else
{
if (a[j].tp) ans[a[j].y] += a[j].tp * sum;
tmp[k++] = a[j++];
}
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= r)
{
if (a[j].tp) ans[a[j].y] += a[j].tp * sum;
tmp[k++] = a[j++];
}
for (int q = l; q <= r; q++) a[q] = tmp[q - l + 1];
}
int main()
{
int n, m, tot = 0, cnt = 0; char ch[8];
scanf("%d", &n);
for (int i = 1, x; i <= n; i++) scanf("%d", &x), pre[i] = pre[i - 1] + x;
scanf("%d", &m);
for (int i = 1, x, y; i <= m; i++)
{
scanf("%s%d%d", ch, &x, &y);
if (ch[0] == 'A') a[++tot].x = x, a[tot].y = y;
else
{
++cnt;
a[++tot].x = y, a[tot].y = cnt, a[tot].tp = 1;
a[++tot].x = x - 1, a[tot].y = cnt, a[tot].tp = -1;
ans[cnt] = pre[y] - pre[x - 1];
}
}
CDQ(1, tot);
for (int i = 1; i <= cnt; i++) printf("%d\n", ans[i]);
}
第二种:
#include
using namespace std;
const int N = 5e5 + 5;
struct node {
int tp, x, y;
}a[N], tmp[N];
inline bool cmp(node p, node q) {return p.x == q.x ? p.y < q.y : p.x < q.x;}
int ans[N], pre[N];
void CDQ(int l, int r)
{
if (l == r) return;
int mid = l + r >> 1, i = l, j = mid + 1, sum = 0;
CDQ(l, mid), CDQ(mid + 1, r);
sort(a + l, a + mid + 1, cmp);
sort(a + mid + 1, a + r + 1, cmp);
while (j <= r)
{
while (i <= mid && a[i].x <= a[j].x)
{
if (!a[i].tp) sum += a[i].y;
++i;
}
if (a[j].tp) ans[a[j].y] += a[j].tp * sum;
++j;
}
}
int main()
{
int n, m, tot = 0, cnt = 0; char ch[8];
scanf("%d", &n);
for (int i = 1, x; i <= n; i++) scanf("%d", &x), pre[i] = pre[i - 1] + x;
scanf("%d", &m);
for (int i = 1, x, y; i <= m; i++)
{
scanf("%s%d%d", ch, &x, &y);
if (ch[0] == 'A') a[++tot].x = x, a[tot].y = y;
else
{
++cnt;
a[++tot].x = y, a[tot].y = cnt, a[tot].tp = 1;
a[++tot].x = x - 1, a[tot].y = cnt, a[tot].tp = -1;
ans[cnt] = pre[y] - pre[x - 1];
}
}
CDQ(1, tot);
for (int i = 1; i <= cnt; i++) printf("%d\n", ans[i]);
}
以下是其他数据结构的运行结果:
树状数组:
线段树:
分块:
二、三维偏序
三维偏序的解决方法有很多,比如树套树。但是(听说)树套树码量大,实现难度较大,那么也可以用CDQ分治去替代一层树。具体实现就是第一维排序,第二维CDQ分治,第三维树状数组/线段树。
2.NKOJ6652 简单题
思路:经典的三维偏序,设时间为第一维,x为第二维,y为第三维。首先时间默认有序,然后第二维用CDQ分治,第三维用树状数组维护。对于查询,把一个查询拆成四个,即\((x1-1,y1-1),-(x1-1,y2),-(x2-1,y1),(x2,y2)\)就可以操作了。
#include
using namespace std;
typedef long long ll;
struct node {
ll x, y, z, tp;
bool operator< (node q) const {
return x == q.x ? y < q.y : x < q.x;
}
}a[1000005];
ll n, x1, y1, x2, y2, z, tot, cnt, c[1000005], ans[1000005], op;
void modify(ll x, ll k)
{
for (ll i = x; i <= n; i += (i & -i)) c[i] += k;
}
ll query(ll x)
{
ll ans = 0;
for (ll i = x; i; i -= (i & -i)) ans += c[i];
return ans;
}
void CDQ(ll l, ll r)
{
if (l == r) return;
ll mid = l + r >> 1, i = l, j = mid + 1;
CDQ(l, mid), CDQ(mid + 1, r);
sort(a + l, a + mid + 1);
sort(a + mid + 1, a + r + 1);
while (j <= r)
{
while (i <= mid && a[i].x <= a[j].x)
{
if (!a[i].tp) modify(a[i].y, a[i].z);
++i;
}
if (a[j].tp) ans[a[j].z] += a[j].tp * query(a[j].y);
++j;
}
for (ll q = l; q < i; q++) if (!a[q].tp) modify(a[q].y, -a[q].z);
}
signed main()
{
scanf("%lld", &n);
while (~scanf("%lld", &op))
{
if (op == 3) break;
if (op == 1) scanf("%lld%lld%lld", &x1, &y1, &z), a[++tot] = node{x1, y1, z, 0};
else
{
scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
a[++tot] = node{x1 - 1, y1 - 1, ++cnt, 1};
a[++tot] = node{x1 - 1, y2, cnt, -1};
a[++tot] = node{x2, y1 - 1, cnt, -1};
a[++tot] = node{x2, y2, cnt, 1};
}
} CDQ(1, tot);
for (ll i = 1; i <= cnt; i++) printf("%lld\n", ans[i]);
}
3.[Violet III]天使玩偶
思路:依然是熟悉的三维偏序,但是比较有意思的是它要找的是曼哈顿距离,即需要处理绝对值,怎么搞呢?答案是把绝对值拆开,用CDQ分治和树状数组,比如先处理左下角,即满足\(t_i < t_j,x_i < x_j,y_i
#include
using namespace std;
char buf[1 << 22], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 22, stdin), p1 == p2) ? EOF : *p1++)
template
inline void rd(T &a)
{
char ch = getchar(); T x = 0;
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
a = x;
}
const int N = 1e6 + 5;
struct node {
int x, y, tp;
}a[N], tmp[N], b[N];
int c[N + 10], cnt, ans[N + 10];
void modify(int x, int k)
{
for (int i = x; i <= N; i += (i & -i)) c[i] = max(c[i], k);
}
void clear(int x)
{
for (int i = x; i <= N; i += (i & -i)) c[i] = -0x3f3f3f3f;
}
int query(int x)
{
int ans = -0x3f3f3f3f;
for (int i = x; i; i -= (i & -i)) ans = max(ans, c[i]);
return ans;
}
void CDQ(int l, int r)
{
if (l == r) return;
int mid = l + r >> 1, i = l, j = mid + 1, k = 1;
CDQ(l, mid), CDQ(mid + 1, r);
while (i <= mid && j <= r)
{
if (a[i].x <= a[j].x)
{
if (!a[i].tp) modify(a[i].y, a[i].x + a[i].y);
b[k++] = a[i++];
}
else
{
if (a[j].tp) ans[a[j].tp] = min(ans[a[j].tp], a[j].x + a[j].y - query(a[j].y));
b[k++] = a[j++];
}
}
while (j <= r)
{
if (a[j].tp) ans[a[j].tp] = min(ans[a[j].tp], a[j].x + a[j].y - query(a[j].y));
b[k++] = a[j++];
}
for (int q = l; q < i; q++) if (!a[q].tp) clear(a[q].y);
while (i <= mid) b[k++] = a[i++];
for (int q = l; q <= r; q++) a[q] = b[q - l + 1];
}
int main()
{
memset(ans, 0x3f, sizeof ans);
memset(c, -0x3f, sizeof c);
int n, m;
rd(n), rd(m);
for (int i = 1, x, y; i <= n; i++)
{
rd(x), rd(y);
tmp[i] = node{x, y, 0};
}
for (int i = n + 1, op, x, y; i <= n + m; i++)
{
rd(op), rd(x), rd(y);
if (op == 1) tmp[i] = node{x, y, 0};
else tmp[i] = node{x, y, ++cnt};
}
for (int i = 1; i <= n + m; i++) a[i] = tmp[i]; CDQ(1, n + m);
for (int i = 1; i <= n + m; i++) a[i] = node{N - tmp[i].x, tmp[i].y, tmp[i].tp}; CDQ(1, n + m);
for (int i = 1; i <= n + m; i++) a[i] = node{tmp[i].x, N - tmp[i].y, tmp[i].tp}; CDQ(1, n + m);
for (int i = 1; i <= n + m; i++) a[i] = node{N - tmp[i].x, N - tmp[i].y, tmp[i].tp}; CDQ(1, n + m);
for (int i = 1; i <= cnt; i++) printf("%d\n", ans[i]);
}
注:这个题就是第二种CDQ写法常数过大然后卡不过去,必须使用第一种写法。
4.「TJOI / HEOI2016」序列
问题描述
佳媛姐姐过生日的时候,她的小伙伴从某宝上买了一个有趣的玩具送给他。
玩具上有一个数列,数列中某些项的值可能会变化,但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性,她想请教你,能否选出一个子序列,使得在任意一种变化中,这个子序列都是不降的?请你告诉她这个子序列的最长长度即可。
输入格式
输入的第一行有两个正整数 ,分别表示序列的长度和变化的个数。
接下来一行有 个数,表示这个数列原始的状态。
接下来 行,每行有两个数 ,表示数列的第 项可以变化成 这个值。
输出格式
输出一个整数,表示对应的答案。
思路:这个题的题意看似有点抽象,其实它所要表达的最重要的东西就一个:若假设数列的第\(i\)的项可能取到的最小值为\(Min[i]\),最大值\(Max[i]\),数列第\(i\)项原来是\(val[i]\),则对于任意的\(j \leq i\),满足\(val[j] \leq Min[i],Max[j] \leq val[i]\),这就是一个显然的三维偏序,第一维显然已经有序,第二维的话CDQ分治,注意排序的话左半部分按照\(Max\)值排序,右半部分按照\(val\)值排序,然后第三维树状数组即可。
#include
using namespace std;
const int N = 1e5 + 5;
struct node {
int val, mn, mx, id, dp;
}a[N];
inline bool cmpmx(node x, node y) {return x.mx < y.mx;}
inline bool cmpval(node x, node y) {return x.val < y.val;}
inline bool cmpid(node x, node y) {return x.id < y.id;}
int c[N];
void modify(int x, int k)
{
for (int i = x; i <= N - 5; i += (i & -i)) c[i] = max(c[i], k);
}
int query(int x)
{
int ans = 0;
for (int i = x; i; i -= (i & -i)) ans = max(ans, c[i]);
return ans;
}
void clear(int x)
{
for (int i = x; i <= N - 5; i += (i & -i)) c[i] = 0;
}
void CDQ(int l, int r)
{
if (l == r) return;
int mid = l + r >> 1, i = l, j = mid + 1;
CDQ(l, mid);
sort(a + l, a + mid + 1, cmpmx);
sort(a + mid + 1, a + r + 1, cmpval);
while (j <= r)
{
while (i <= mid && a[i].mx <= a[j].val) modify(a[i].val, a[i].dp), ++i;
a[j].dp = max(a[j].dp, query(a[j].mn) + 1), ++j;
}
for (int q = l; q < i; q++) clear(a[q].val);
sort(a + mid + 1, a + r + 1, cmpid);
CDQ(mid + 1, r);
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1, x; i <= n; i++)
{
scanf("%d", &x);
a[i] = node{x, x, x, i, 1};
}
for (int i = 1, x, y; i <= m; i++)
{
scanf("%d%d", &x, &y);
a[x].mn = min(a[x].mn, y);
a[x].mx = max(a[x].mx, y);
} CDQ(1, n); int ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, a[i].dp);
printf("%d", ans);
}