cdq初步
cdq分治 三维偏序问题
在分享题目的时候听闻有同学说cdq分治，之后便去研究了一番，发现cdq分治的思想与之前这道动态的区间重叠查询有着异曲同工之妙。
以经典的三维偏序为例。
对三个值按照第一、第二、第三优先级的顺序进行升序排序，在排好序的新序列上进行**“归并”，假设当前对区间$[l, r]$进行归并。那么由于我们的良好的排序规则**，可以保证$[mid + 1, r]$中的三元组一定不会对区间$[l, mid]$中的三元组产生贡献。换言之，可能产生贡献的三元组们要么同时存在于某个子区间内，要么是左区间对右区间产生贡献。因而我们进行双指针归并排序，排序时不断比较的是三元组的$y$属性，而插入三元组时维护一颗以三元组的$z$属性构成的支持区间加，区间清零，区间查询和的权值线段树，通过在权值线段树上不断地更新、查询来维护最终的答案。
有两个值的注意的点：
- 可能会出现重复元素，因而我们要对原始三元组序列去重，给重复的三元组加一个权值，最后在计算答案的时候分别对相同的三元组之间和不同的三元组之间统计答案。
- “良好的排序规则”是很重要的。最开始按照个人的理解仅仅按照三元组的$x$属性进行排序，但是这样就无法保证归并时右儿子一定不对左儿子做贡献，从而使cdq分治失去了根本的理论保证。
** 虽然借此知道了对所有分量都维护顺序的序列是很有必要的，但是回头再去看区间重叠的问题，仍然不甚理解出现在那题中的问题。因为在那题中不需要考虑左右儿子彼此的贡献，而仅仅只需要一个顺序来建树而已。qaq神秘
1#define ls (p << 1)
2#define rs ((p << 1) | 1)
3#define mid ((l + r) >> 1)
4
5const int maxn = 1e5 + 10;
6//权值线段树: 单点置值，区间查询
7struct ST{
8 static const int maxn = 2e5 + 10;
9 int st[maxn << 2];
10 void add(int p, int l, int r, int k, int x){
11 if(l == r && l == k){
12 st[p] += x; return;
13 }
14 if(k <= mid) add(ls, l, mid, k, x);
15 else add(rs, mid + 1, r, k, x);
16 st[p] = st[ls] + st[rs];
17 }
18 void clear(int p, int l, int r, int k){
19 if(l == r && l == k){
20 st[p] = 0; return;
21 }
22 if(k <= mid) clear(ls, l, mid, k);
23 else clear(rs, mid + 1, r, k);
24 st[p] = st[ls] + st[rs];
25 }
26 int query(int p, int l, int r, int L, int R){
27 if(L <= l && r <= R) return st[p];
28 int ans = 0;
29 if(L <= mid) ans += query(ls, l, mid, L, R);
30 if(R > mid) ans += query(rs, mid + 1, r, L, R);
31 return ans;
32 }
33}st;
34struct NODE{
35 int x, y, z, w;
36 bool operator < (const NODE& b)const{
37 if(x != b.x) return x < b.x;
38 if(y != b.y) return y < b.y;
39 return z < b.z;
40 }
41 bool operator == (const NODE &b)const{
42 return x == b.x && y == b.y && z == b.z;
43 }
44 void read(){scanf("%d %d %d", &x, &y, &z); w = 1;}
45 void prt(){printf("(%d %d %d) : %d\n", x, y, z, w);}
46};
47NODE temp[maxn], node[maxn];
48
49
50int f[maxn];
51vector<int> vec[maxn << 2];
52bool cmp(int i, int j){return node[i].y < node[j].y;}
53void sove(int p, int l, int r){
54 if(l == r){
55 vec[p].push_back(l);
56 return ;
57 }
58 sove(ls, l, mid);
59 sove(rs, mid + 1, r);
60 int i = 0, j = 0;
61 while(i < mid - l + 1 && j < r - mid){
62 if(node[vec[ls][i]].y <= node[vec[rs][j]].y){
63 st.add(1, 1, 200000, node[vec[ls][i]].z, node[vec[ls][i]].w);
64 vec[p].push_back(vec[ls][i]);
65 i++;
66 }
67 else{
68 f[vec[rs][j]] += st.query(1, 1, 200000, 1, node[vec[rs][j]].z);
69 vec[p].push_back(vec[rs][j]);
70 j++;
71 }
72 }
73 while(i < mid - l + 1){
74 st.add(1, 1, 200000, node[vec[ls][i]].z, node[vec[ls][i]].w);
75 vec[p].push_back(vec[ls][i]);
76 i++;
77 }
78 while(j < r - mid){
79 f[vec[rs][j]] += st.query(1, 1, 200000, 1, node[vec[rs][j]].z);
80 vec[p].push_back(vec[rs][j]);
81 j++;
82 }
83 for(auto x: vec[p]) st.clear(1, 1, 200000, node[x].z);
84}
85
86int ans[maxn];
87
88int main(){
89// Fastin;
90 int n, d; scnaf("%d %d", &n, &d);
91 for(int i = 1; i <= n; i++) temp[i].read();
92 sort(temp + 1, tmep + 1 + n);
93 int m = 0;
94 node[++m] = temp[1];
95 for(int i = 2; i <= n; i++){
96 if(temp[i] == temp[i - 1]) node[m].w++;
97 else node[++m] = temp[i];
98 }
99
100 sove(1, 1, m);
101 for(int i = 1; i <= m; i++) f[i] += node[i].w - 1;
102 fro(int i = 1; i <= m; i++) ans[f[i]] += node[i].w;
103 for(int i = 0; i < n; i++) printf("%d\n", ans[i]);
104 return 0;
105}