似乎題解區并沒有 cdq 套 cdq 的作法，剛好今天講了，就來寫一發。

題意與記號

題目講的很清楚了。此方法并沒有樹狀數組好想也沒有其高效，但能很方便擴展。下文記原序列為 $d$，將每個點拆分成點與詢問，內部增加一個名為 $id$ 的數據，若其為 $?1$，則是點，否則是詢問。

使用類 c++ 數組的書寫方式，否則角標太復雜實在不好看。下文先講二維再講三維。

二維偏序

先對 $x$ 維排序，再分治 $y$ 維，每一次分治中點為 $mid$ 的區間 $[l,r)$，我們都能保證，也必須保證 $d[a].x\le d[b].x$，$a\in [l,mid)$，$b\in [mid,r)$。
L={d[l],d[l+1],d[l+2],…?}????????????????????????????????????????????????↑R={d[mid],d[mid+1],…?}????↑ L=\{d[l],d[l+1],d[l+2],\dots \} \\ \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \uparrow \\ R=\{d[mid],d[mid+1],\dots \} \\ \!\! \uparrow L={d[l],d[l+1],d[l+2],…}↑R={d[mid],d[mid+1],…}↑
我們對兩邊同時向后處理（并非同步），我們正在處理 $d[a]$ 與 $d[b]$，其中 $d[a].id=?1$ 與 $d[b].id\ne ?1$（其它情況不用考慮）。

如果 $d[a].y\le d[b].y$，由于分治，$L$ 與 $R$ 內以 $y$ 為關鍵字肯定是有序的，所以 $d[a^{\prime }].y\le d[b^{\prime }].y$，$a^{\prime }\in [l,a]$，$b^{\prime }\in [b,r]$。

所以此時我們便可以記錄 $d[a]$ 的貢獻（這里是 $1$），并將 $d[a]$ 扔到歸并排序的輔助數組里， $a\leftarrow a+1$。

同理，如果 $d[a].y>d[b].y$，我們直接由之前的貢獻總和便可以計算答案，并將 $d[b]$ 扔到歸并排序的輔助數組里，$b\leftarrow b+1$。

三維偏序

進入正題，仿照上面的方法，在第一次 cdq 內部，每一層再執行另一種 cdq（cdq2），如果我們能保證 $L$ 與 $R$ 內部同時關于 $x$ 與 $y$ 有序就好了，可是我們在分治的過程中必然會將 $x$ 打亂，如果有一種方法，能告訴我們 $x$ 曾經在哪邊，便能夠解決這個問題。

也就是說：我們只想要曾經（$x$ 維）在左邊點的對右邊詢問的做貢獻。

為此，我們擴展 $d$，加入一個名為 $tag$ 的數據表示在當層是在左邊還是右邊，由于此時 $y$ 早已有序，仿照二維進行 cdq2。
解釋見代碼吧，超詳細的！

namespace PB {node d[N];                                             // 存儲當前處理的節點數組，包含點和查詢void solve(int l, int r) {                             // 處理區間 [l, r) 的 z 維偏序if (l == r - 1) return;                            int mid = (l + r) >> 1;                            solve(l, mid), solve(mid, r);                      int a = l, b = mid, c = l, sum = 0;                // sum 記錄左邊點的數量while (a < mid || b < r) {                         // 歸并排序，按 z 坐標合并if (b == r || (a < mid && d[a].z <= d[b].z)) { // 左邊還有元素且 z 更小（或右邊已空）if (d[a].id == -1 && d[a].tag == LEFT)     // 如果是左邊區間的一個點++sum;                                 tp[c++] = d[a++];                          } else {                                       // 右邊 z 更小（或左邊已空）if (d[b].id != -1 && d[b].tag == RIGHT)    // 如果是右邊區間的查詢anst[d[b].id] += sum;                  // 累加當前左邊點的數量到查詢結果tp[c++] = d[b++];                          }}copy(tp + l, tp + r, d + l); // 將臨時數組復制回原數組，完成歸并}
} // namespace PBnamespace PA {void solve(int l, int r) {                             // 處理區間 [l, r) 的 y 維偏序if (l == r - 1) return;                            int mid = (l + r) >> 1;                            solve(l, mid), solve(mid, r);                      // 遞歸處理左半區間 [l, mid) 和右半區間 [mid, r)int a = l, b = mid, c = l;                         // a, b 分別指向左右區間，c 指向臨時數組while (a < mid || b < r) {                         // 歸并排序，按 y 坐標合并if (b == r || (a < mid && d[a].y <= d[b].y)) { // 左邊還有元素且 y 更小（或右邊已空）d[a].tag = LEFT, tp[c++] = d[a++];         // 標記為左區間} else {                                       // 右邊 y 更小（或左邊已空）d[b].tag = RIGHT, tp[c++] = d[b++];        // 標記為右區間}}copy(tp + l, tp + r, d + l);     // 將臨時數組復制回原數組，完成 y 維歸并copy(tp + l, tp + r, PB::d + l); // 將排序后的數組復制到 PB 命名空間的 d 數組PB::solve(l, r);                 // 調用 PB 處理 z 維偏序}
} // namespace PA

時間復雜度

PB 中一次處理長度為 $n$ 的區間 $O(n)=n\log n$。

PA（總）：$O({\sum }_{i=0}^{\log n}T(\frac{n}{2^i})\times 2^i)=O(n{\log }^{2}n)$ 。