我只是个萌新,写一篇学习笔记,希望可以帮助未来的自己和他人。如果有大佬看到了错误,您可以在评论区或者私信中指出,并且我非常欢迎您的纠错。
本博客还是从二维偏序开始铺垫,对cdq分治进行讲解(实际上是给自己讲,因为没人看)。
前置知识:归并排序
cdq分治的学习需要保证对归并排序的理解,虽然它是一个基础算法。
给定 \(n\) 个元素,第 \(i\) 个元素有两个属性 \(a_i\) 和 \(b_i\) ,设 \(f(i)\) 为满足 \(a_j \leq a_i,b_j \leq b_i,j \neq i\) 的 \(j\) 的个数,对于每一个 \(0 \leq d \leq n - 1\) ,求满足 \(f(i) = d\) 的 \(i\) 的个数。
我们可以发现,对于一个元素 \(i\) ,只有满足 \(a_j \leq a_i\) 的元素才有可能对 \(f(i)\) 产生贡献。
不就是要单个属性小于等于吗,太简单了!我们只需要对属性 \(a\) 单独排序即可!
那么属性 \(b\) 呢?注意到对 \(f(i)\) 有贡献的元素要满足 \(b_j \leq b_i\) ,那么在排序后,我们需要获取在某个元素前面的满足 \(b_j \leq b_i\) 的个数,这一部分显然使用值域 BIT ,按顺序跑元素,然后一个一个加入,然后求前缀和即可。
有一个问题,如果两个元素的 \(a\) 相同,然而 \(b\) 小一点的排到了后面,会发生什么?
这一个的贡献算不到了。
所以,在 \(a\) 相同的元素内,我们应该对 \(b\) 排序。
所以 cmp 函数长这个样子:
bool cmp(node x,node y){ if(x.a != y.a)return x.a < y.a; return x.b < y.b; }
到目前为止,我相信能来学 cdq 分治的大佬肯定能理解二维偏序,那么就进入我们的正题了:
P3810
在二维偏序中,我们在满足 \(a\) 有序的情况下,对 \(b\) 使用值域 BIT 得到了答案。
现在三维偏序多了一个属性,我们无法在一次排序内对两个属性进行排序,怎么办呢...
对新进来的属性进行归并排序。
假设我们一开始排序 \(a\) ,对 \(b\) 跑归并,对 \(c\) 用值域 BIT。
在归并排序的过程中,分析左边区间对右边区间的贡献。
为什么可以这样算?
由于归并排序是把原来的数组拆成一半一半的小区间,在拆的过程中我们未曾改变顺序,所以第一次开始算的时候,\(a\) 是有序的!
然后,我们合并区间上去,由于我们之前只是在小区间内合并,对于右边的大区间,我们的 \(a\) 仍然是有序的!
所以,我们可以直接分析左边区间对右边区间的贡献了(右边区间内部自己的贡献,和左边区间内部自己的贡献并不在考虑范围内,这部分会在之前更小的区间的归并排序过程中计算出来)。
这部分长这个样子。
void solve(int l,int r){ int mid = (l + r) / 2; if(l == r)return ; solve(l,mid); solve(mid + 1,r); int posl = l,posr = mid + 1; int tot = l; while(posl <= mid && posr <= r){ if(e[posl].b <= e[posr].b){ t.update(e[posl].c,e[posl].cnt); tmp[tot ++] = e[posl ++]; } else { e[posr].val += t.query(e[posr].c); tmp[tot ++] = e[posr ++]; } } while(posl <= mid){ t.update(e[posl].c,e[posl].cnt); tmp[tot ++] = e[posl ++]; } while(posr <= r){ e[posr].val += t.query(e[posr].c); tmp[tot ++] = e[posr ++]; } for(int i = l;i <= mid;i ++)t.update(e[i].c,-e[i].cnt); for(int i = l;i <= r;i ++)e[i] = tmp[i]; }
解释一下,这个题有重点,这个 cnt 就是与这个点相同的点的个数。
f 就是这个元素的函数值。
在“并”的过程中,我们保证了 \(b\) 一定是排序好的,既然如此,我们就可以对 \(c\) 用值域 BIT 了。对于左边的区间,进行一个值域树状数组的加,对于右边的区间,直接在值域 BIT 中属性 \(c\) 小于它的个数,值域 BIT 里面只有左区间的元素,所以这就是左区间对右区间的贡献。
这个题就结束了。
由于 cdq分治 只能一次性处理完,所以跑 cdq分治 需要如下条件:
修改操作对询问的贡献独立,修改操作相互不影响
题目可以离线处理
cdq分治(在这个题中)实际上帮助我们做到的是通过对时间复杂度增加一个log来降维。
那么,跟上面讲解一样的,在cdq分治中,对于划分出来的两个区间,前一个子问题需要用来解决后一个子问题。
想必到这里,不会有人不懂了吧(
不懂欢迎问我。
贴上完整代码。
#include<bits/stdc++.h> #define int long long #define mem(x,y) memset(x,y,sizeof(x)) #define frein freopen("in.in","r",stdin) #define freout freopen("out.out","w",stdout) #define debug(x) cout << (#x) << " = " << x << endl; using namespace std; int read(){ int s = 0,w = 1; char ch = getchar(); while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();} while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar(); return s * w; } int MAXM; int lowbit(int x){return x & -x;} struct BIT{ int e[200010]; void update(int i,int x){for(;i <= MAXM;i += lowbit(i))e[i] += x;} int query(int i){ int s = 0; for(;i;i -= lowbit(i))s += e[i]; return s; } }t; struct node{ int a; int b; int c; int cnt; int val; }e[100010],tmp[100010]; int n; int ans[100010]; int cnt = 1; bool cmp(node x,node y){ if(x.a != y.a)return x.a < y.a; if(x.b != y.b)return x.b < y.b; return x.c < y.c; } void solve(int l,int r){ int mid = (l + r) / 2; if(l == r)return ; solve(l,mid); solve(mid + 1,r); int posl = l,posr = mid + 1; int tot = l; while(posl <= mid && posr <= r){ if(e[posl].b <= e[posr].b){ t.update(e[posl].c,e[posl].cnt); tmp[tot ++] = e[posl ++]; } else { e[posr].val += t.query(e[posr].c); tmp[tot ++] = e[posr ++]; } } while(posl <= mid){ t.update(e[posl].c,e[posl].cnt); tmp[tot ++] = e[posl ++]; } while(posr <= r){ e[posr].val += t.query(e[posr].c); tmp[tot ++] = e[posr ++]; } for(int i = l;i <= mid;i ++)t.update(e[i].c,-e[i].cnt); for(int i = l;i <= r;i ++)e[i] = tmp[i]; } signed main(){ cin>>n>>MAXM; for(int i = 1;i <= n;i ++){ e[i].a = read(),e[i].b = read(),e[i].c = read(); e[i].cnt = 1; } sort(e + 1,e + n + 1,cmp); for(int i = 2;i <= n;i ++){ if(e[i].a == e[cnt].a && e[i].b == e[cnt].b && e[i].c == e[cnt].c)e[cnt].cnt ++; else e[++ cnt] = e[i]; } solve(1,cnt); for(int i = 1;i <= cnt;i ++)ans[e[i].val + e[i].cnt - 1] += e[i].cnt; for(int i = 0;i <= n - 1;i ++)printf("%lld\n",ans[i]); return 0; }
这个博客还没完,还会有一些简单例题。
关于整体二分:
请叫我填坑。
2022.2.23 13:24