咕了很久的 \(\text{cdq}\) 终于开始学了。
中间翻了很多博客，最后是看这一篇看懂的。讲的不算详细，但是要点基本都有。
\(三维偏序问题\)
就比如臭名昭著大名鼎鼎的陌上花开
设 \(f(i)\) 为 对于 \(\forall j \not= i\)，满足 \(a_i \leq a_j, b_i \leq b_j, c_i \leq c_j\) 的 \(j\) 的数量。本题要求的是 \(\forall d \in [0, n), f(i) = d\) 的数量。
cdq解决此问题的思路十分巧妙，也十分好理解。
-
首先按照第一维 \(a_i\) 排序，这样就满足了 \(a_i\) 的单调性。
-
去重。将 \(a_i, b_i, c_i\) 相同的给缩成一个，记录到 \(cnt_i\) 里表示有多少个和 \(i\) 相同的。
-
分治递归子区间 \([l, mid]\) 和 \([mid+1, r]\)，将两个指针 \(i, j\) 分别指向 \(l, mid+1\)，然后开始扫这两个区间。
-
由于计算的是左区间对右区间产生的影响，所以扫右区间，同时将左区间满足 \(b_i \leq b_j\) 的点加入权值树状数组(为了求前缀和)，其中 \(c_i\) 作为下标加入，加入的值即为 \(cnt_i\)。
-
对于每个右端点，查询比他的 \(c_j\) 小的数量，将其扔进这个点的答案数组即可。(注意此时的 \(j\) 是 \(f(i)\) 中的 \(i\))
code
#include <iostream>
#include <algorithm>
#define GMY (520&1314)
#define char_phi int
#define re register int
#define FBI_OPENTHEDOOR(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#define Endl cout << '\n'
#define _ ' '
#define Dl cerr << '\n'
#define DMARK cerr << "###"
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 100005
#define MXS 200005
using namespace std;
inline void Fastio_setup(){ ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); }
/*
学cdq来了
*/
int n, mxs, final_ans, tmpn;
int ans[N];
struct Element {int x, y, z, cnt, answer;};
struct TreeArray{
#define lowbit(x) ((x) & (-(x)))
int C[MXS];
inline void Update(int k, int w){
while (k <= mxs)
C[k] += w, k += lowbit(k);// , cerr << k << '\n';// , DMARK;
}
inline int Query(int k){
int res(0);
while (k != 0)
res += C[k], k -= lowbit(k);
return res;
}
};
struct Element arr[N], a[N];
struct TreeArray TA;
inline bool compx(Element A, Element B){ return ( (A.x == B.x) ? ( (A.y == B.y) ? (A.z < B.z) : (A.y < B.y) ) : (A.x < B.x) ); }
inline bool compy(Element A, Element B){ return ( (A.y == B.y) ? ( (A.x == B.x) ? (A.z < B.z) : (A.x < B.x) ) : (A.y < B.y) ); }
#define mid ((L+R)>>1)
void cdq(int L, int R){
// cerr << "cdq: " << L << _ << R << '\n';
if (L == R)
return ;
cdq(L, mid); cdq(mid+1, R);
sort(a+L, a+mid+1, compy); sort(a+mid+1, a+R+1, compy);// 我才想到第二个传的参应当是右区间-1。。
int l = L, r = mid+1;
while (r <= R){
while (l <= mid and a[l].y <= a[r].y)
TA.Update(a[l].z, a[l].cnt), l ++;
a[r].answer += TA.Query(a[r].z);
r ++;
}
for (re i = L ; i <= l-1 ; ++ i)
TA.Update(a[i].z, -a[i].cnt);
/*int l = L, r = mid+1;
while (l <= mid){
while (r <= R and a[l].y <= a[r].y)
TA.Update(a[r].z, a[r].cnt), r ++;
a[l].answer += TA.Query(a[l].z);
l ++;
}
// 有单调性，所以最后再清空是正确的
for (re i = mid+1 ; i <= r-1 ; ++ i)// 注意终点不是R，因为可能r到不了R
TA.Update(a[i].z, -a[i].cnt);*/
}
#undef mid
inline void work(){
cin >> tmpn >> mxs;
for (re i = 1, x, y, z ; i <= tmpn ; ++ i)
{cin >> x >> y >> z; arr[i] = (Element){x, y, z, 0};}
sort(arr+1, arr+tmpn+1, compx);
for (re i = 1, num(0) ; i <= tmpn ; ++ i){
num ++;
if (arr[i].x != arr[i+1].x or arr[i].y != arr[i+1].y or arr[i].z != arr[i+1].z)
a[++ n] = arr[i], a[n].cnt = num, num = 0;
}
cdq(1, n);
// DMARK;
for (re i = 1 ; i <= n ; ++ i)
ans[a[i].answer+a[i].cnt-1] += a[i].cnt;
/*for (re i = 0 ; i <= tmpn-1 ; ++ i)
cerr << ans[i] << _;
Dl;*/
for (re i = 0 ; i <= tmpn-1 ; ++ i)
cout << ans[i] << '\n';
}
#undef int
// #define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(a, a);
#endif
Fastio_setup();
work();
return GMY;
}
\(\text{sto}\) 权值树状数组 \(\text{orz}\)
标签：浅谈,int,text,分治,leq,cdq,区间,define From： https://www.cnblogs.com/charphi/p/16793526.html