---
title: '離線演算法'
disqus: hackmd
---
###### tags:`2023 NYCU PCCA Winter Camp`
離線演算法
===
[TOC]
# 離線演算法
## 在線v.s.離線
:::danger
* 現在想像你有一台機器，你有很多問題想請它回答。
* 在線:你問它一個問題，它會馬上告訴你答案。
* 離線:你必須把所有操作都先給它，它才能處理這些操作，最後一起輸出所有答案。
* 題目可以離線，代表你可以隨意決定處理操作的順序。
* 有些題目離線處理 Coding 複雜度會降低不少，通常可以避開持久化資結或更噁心的資結。
* 但碰到強制在線就只能乖乖寫又臭又長的資結。而題目要出成強制在線通常有兩種方法:
-- 互動式 I/O:你要輸出答案 judge 才會讓你讀下一筆詢問。
-- Hash:每筆詢問會跟上一筆詢問的答案 hash，judge 會給你 hash 後的結果。
:::

# 莫隊算法
#### 起源
* 2009 年由 IOI 中國集訓隊隊長莫濤發明並發揚光大。
* 莫隊 = (莫) 濤 + (隊) 長
* 優化區間詢問的演算法。
* 有一說其實在莫濤之前這個算法就已經出現，莫濤只是做了比較完整的統整。
#### 使用時機例子:區間查詢
有一個長度為 $N$ 的序列，接著有 $Q$ 筆詢問(區間和、區間眾數)。
每筆詢問給區間 $[ql, qr]$，求這個區間的答案，可以離線做。
* $N、Q$ 很大，時間複雜度$O(NQ)$會吃TLE。
* 方便起見，以下假設 $N、Q$ 是同個量級的，也就是說暴力是 $O(N^2)$。

## 仙貝知識1.答案窗口
### 核心概念
:::info
* 我們用另外一個角度看區間詢問。
* 試著維護一個「答案窗口」。
* 當這個窗口對到的區間是 $[l, r]$ 時，代表這個窗口所維護的值正好是詢問 $[l, r]$ 這個區間的答案。
* 假設現在答案窗口停留在 $[l, r]$ ，而我們要回答 $[ql, qr]$ 這個區間的答案。

Question:那我們要把這個窗口「滾動」到 $[ql, qr]$ 。
Answer:怎麼移動?方法有兩種:把窗口延伸或內縮。

實作方法
* 延伸(區間變大):窗口左界往左一格 $(l--)$ ，或是右界往右一格 $(r++)$ 。
* 內縮(區間變小):窗口左界往右一格 $(l++)$ ，或是右界往左一格 $(r--)$ 。

Answer:利用延伸和內縮滾動窗口，把窗口滾到詢問區間，如此依序處理完所有詢問。
:::
### 實作優化
:::success
* 瓶頸一:窗口延伸/內縮一格的時間。
* 瓶頸二:窗口延伸/內縮一格的次數。

先忽略瓶頸一，假設可以 O(1) 把窗口的邊界移動一格。

Question:如何降低移動窗口的次數?
Answer:窗口移動次數取決於你處理詢問區間的順序 ⇒ 降低窗口移動次數。

Question:如何安排區間的處理順序?
Answer:「先排左再排右」，也就是「把所有詢問先按左界排序，左界相同則按右界排序」?

但這最差情況還是 $O(N^2)$ 。反例:$[1, 1], [1, N], [2, 2], [2, N], [3, 3], [3, N], \cdots$，移動到下個詢問最差 $O(N)$ ，總共移動 $O(N)$ 次，最差 $O(N^2)$。

Answer:莫隊算法
:::
## 莫隊算法實作
### 實作流程
:::success
1. 把序列每 $\sqrt{N}$ 個分成一塊。
2. 把所有詢問先按「左界所在的塊」排序。
3. 若左界所在的塊相同，則按右界排序。
4. 滑動次數降為$O(N\sqrt{N})$。
:::
### 滑動次數證明(Q=N)
1. 假設塊的大小和數量都是 $O(\sqrt{N}$) 。
2. 窗口左界複雜度證明
* 當處理完此詢問，要滾動到下一個詢問時，窗口左界的指針移動情形有兩種:在同一塊內移動、移動到下一個塊。
* 因為塊的大小是 $O(\sqrt{N}$) ，所以這兩種情形都是 $O(\sqrt{N}$) 。
* 總共 O(N) 個詢問 ⇒ 窗口左界移動次數 $O(N\sqrt{N}$) 。

3. 窗口右界複雜度證明
4. 總時間複雜度$O(N\sqrt{N})$ 。
* 窗口左界、窗口右界移動次數都是 $O(N\sqrt{N})$ 。
* 移動一格的複雜度剛剛假設是 O(1)。
* 故總時間複雜度 $O(N\sqrt{N})$ 。
### 滑動次數證明(Q≠N)
1. 假設我們能 O(1) 將窗口伸縮一格、塊的大小為 B。
2. 窗口左界:移動到下個詢問只要 $O(B)$，所以總移動次數 $O(QB)$。
3. 窗口右界:在左界同塊的詢問之間移動均攤 $O(N)$ ，總共有 $O(NB)$ 塊，故總移動次數 $O(N^2B)$ 。
4. 合併兩者可得總複雜度 $O(QB+N^2B)$ 。
5. 根據算幾不等式， $B$ 取 $\frac{N}{\sqrt{Q}}$時，有最佳複雜度 O(N√Q)$ 。
### 一些細節
* 假設將窗口伸縮一格不是 $O(1)$ ，而是 $O(f(x))$ 。
* 那複雜度會變成 $O(f(x)N\sqrt{Q})$ ，就是多乘 $O(f(x))$ 就對了。
舉例:假設伸縮一格要 $O(log N)$ ，那複雜度就是 $O(N\sqrt{Q} log N)$ 。
* 莫隊只是幫你優化窗口的移動次數，拔掉一個根號，
* 想砸莫隊的話你得想辦法讓 $O(f(x))$ 盡量小，最好 $O(1)$ 或 $O(log N)$ 。
* 另外，莫隊算法受常數影響非常大，==理論最佳複雜度不代表執行時間最少==。
* 可利用 judge 或本機生大測資三分搜塊的大小。

## 例題一. 區間和
有一個長度為 $N$ 的序列 $⟨a_N⟩$，接下來有 $Q$ 筆詢問。
每筆詢問給 $[l, r]$，求 $\sum ^r_{i=l}a_i$ 。

限制
* $N, Q \leq 1e5$
## 例題一. AC code

#define ll long long
#define pll pair<ll,ll>
#define F first 
#define S second
#define ql F.F
#define qr F.S
#define id S
const ll MAXN=2e5+5;

int N,Q,B;
vector<ll> a;
vector<pair<pll,ll>> qry;
ll ans[MAXN];

void init{
    cin>>N>>Q;
    B=N/max((ll)sqrt(Q),1);//B:塊的大小
    
    a.clear();a.resize(N);
    qry.clear();qry.resize(Q);
    for(auto& i:a) cin>>i;
    
    int cnt=0;
    for(auto& i:qry){
        cin>>i.ql>>i.qr;
        i.ql--;i.qr--;//轉換成0-base
        i.id=cnt++;//先用
    }
}

void solve(){
    sort(qry.begin(),qry.end(),
         [&](const pair<pll,ll>& a,const pair<pll,ll>& b){
        if(a.ql/B==b.ql/B)    return a.qr<b.qr;
        //左界區塊相同，按右界排
        else    return a.ql/B<b.ql/B;
        //否則按左界的區塊來排序
    });
    
    ll l=0,r=-1;//答案窗口,初始化為[0, -1]
    ll sum=0;////答案窗口維護的值(也就是窗口的區間和)
    
    for(auto& i:qry){
        while(l>i.ql) sum+=a[--l];//延伸左界
        while(r<i.qr) sum+=a[++r];//延伸右界
        while(l<i.ql) sum-=a[l++];//內縮左界
        while(r>i.qr) sum-=a[r--];//內縮右界
        ans[i.id]=sum;
    }
    
    for(ll i=0;i<Q;i++) cout<<ans[i]<<'\n';
}

### 實作細節
:::success
1. 因為會把詢問重新排序處理，因此要記錄一下詢問的時間點、開個 ans 陣列存，最後再一起輸出。
2. 順序上是先延伸再內縮，不然答案窗口 $[l, r]$ 可能會出現 l > r 的情況(在某些題目會出錯)。
:::
## 例題二.[區間數字種類數 CSES Distinct Values Queries](https://cses.fi/problemset/task/1734/)

給一個長度為 $N$ 的序列，接下來有 $Q$ 筆詢問。每筆詢問 $[l, r]$，求區間 $[l, r]$ 有幾種數字?

限制
* $N, Q \leq 2 \times 1e5$、$a_i \leq 1e9$
### 解題關鍵
:::info
1. 維護一個答案窗口。
2. 開一個變數 $ans$ 代表這個窗口對應到的答案。
3. 開一個陣列 $cnt$，$cnt[x]$ 紀錄 $x$ 出現多少次。
4. 加入一個數字 $x$(延伸窗口):$cnt[x]++$
5. 拔掉一個數字 $x$(延伸窗口):$cnt[x]--$
6. 當有數字的出現次數不再是 $0$ 或變成 $0$ 就要改變 $ans$。
7. $a_i \leq 1e9$ ⇒ 離散化
:::
### 例題二. AC code
:::success

#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(false),cin.tie(0);
#define ll long long
#define pll pair<ll,ll>
#define eb emplace_back
#define F first
#define S second
#define ql F.F
#define qr F.S
#define id S

const ll MAXN=2e5;
ll N,Q,B;
vector<ll> a,dis;//dis存離散
vector<pair<pll,ll>> qry;
ll cnt[MAXN];
ll ans[MAXN];
void init(){
  cin>>N>>Q;
  B=N/max((int)sqrt(N),1);
  
  a.clear(),qry.clear();
  a.resize(N),qry.resize(Q);

  for(auto& i:a) {
    cin>>i;
    dis.eb(i);
  }
  
  sort(dis.begin(),dis.end());
  dis.resize(unique(dis.begin(),dis.end())-dis.begin());
  for(ll i=0;i<N;i++){
    a[i]=lower_bound(dis.begin(),dis.end(),a[i])-dis.begin();
  }
  
  ll cnt=0;//0-base
  for(auto& i:qry){
    cin>>i.ql>>i.qr;
    i.ql--;i.qr--;
    i.id=cnt++;
  }
}
void solve(){
  sort(qry.begin(),qry.end(),[&](const pair<pll,ll>& a,const pair<pll,ll> b){
    if(a.ql/B==b.ql/B) return a.qr<b.qr;
    else return a.ql/B<b.ql/B;
  });  
  
  ll l=0,r=-1,total=0;//左閉右閉
  for(auto& i:qry){
    while(l>i.ql){
      l--;
      cnt[a[l]]++;
      if(cnt[a[l]]==1) total++;
    }
    while(r<i.qr){
      r++;
      cnt[a[r]]++;
      if(cnt[a[r]]==1) total++;
    }
    while(l<i.ql){
      cnt[a[l]]--;
      if(cnt[a[l]]==0) total--;
      l++;
    }
    while(r>i.qr){
      cnt[a[r]]--;
      if(cnt[a[r]]==0) total--;
      r--;
    }
    ans[i.id]=total;
  }
  for(ll i=0;i<Q;i++) cout<<ans[i]<<'\n';
}
int main() {
  fastio
  init();
  solve();
  return 0;
}

:::
## 例題三.[TIOJ 2122 區區區間眾數](https://tioj.ck.tp.edu.tw/problems/2122)

給一個長度為 $N$ 的序列，接下來有 $Q$ 筆詢問。每筆詢問 $[l, r]$，輸出區間 $[l, r]$ 眾數的出現次數。

限制
* $N, Q \leq 1e5$、$a_i \leq 1e5$

### 解題關鍵
:::info
1. 新的 $max$ 只有兩種可能:維持不變或減 $1$。
2. 維持不變表示有其他眾數存在。
3. 減 $1$ 表示只有被拔掉的那個數字的 $cnt$ 等於 $max$。
4. 開一個陣列 $cntcnt$，維護「出現次數的次數」。
5. 也就是在原本的 $cnt$ 陣列上套一層 $cnt$。
6. 舉例:$cntcnt[1] = 2$ 代表出現次數是 $1$ 的數字有 $2$ 種。
7. 維護好 $cnt$ 跟 $cntcnt$ ，就可以好好處理拔掉數字的情況了!
:::
### 例題三. AC code

:::success

#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(false),cin.tie(0);
#define ll long long
#define pll pair<ll,ll>
#define ql first.first
#define qr first.second
#define id second
#define _ <<' '<<

const ll MAXN=1e5+5;

ll N,Q,B;
vector<ll> a;
vector<pair<pll,ll>> qry;
ll ans[MAXN],cnt[MAXN],cntcnt[MAXN];

void init(){
  cin>>N>>Q;
  B=N/(ll)sqrt(Q);
  
  a.clear(),a.resize(N);
  qry.clear(),qry.resize(Q);
  
  for(auto& i:a) cin>>i;

  ll cnt=0;
  for(auto& i:qry){
    cin>>i.ql>>i.qr;//0-base
    i.ql--;i.qr--;
    i.id=cnt++;
  }
}

void solve(){
  sort(qry.begin(),qry.end(),[&](const pair<pll,ll>& a,const pair<pll,ll>& b){
    if(a.ql/B==b.ql/B) return a.qr<b.qr;
    else return a.ql/B<b.ql/B;
  });
  
  ll l=0,r=-1,showmax=0;
  for(auto& i:qry){
    while(l>i.ql){
      l--;
      cntcnt[cnt[a[l]]]--;
      cnt[a[l]]++;
      cntcnt[cnt[a[l]]]++;
      if(cntcnt[showmax+1]!=0) showmax++;
    }
    while(r<i.qr){
      r++;
      cntcnt[cnt[a[r]]]--;
      cnt[a[r]]++;
      cntcnt[cnt[a[r]]]++;
      if(cntcnt[showmax+1]!=0) showmax++;
      // cout<<'l' _ l _ 'r' _ r _ "showmax" _ showmax<<'\n';
    }
    while(l<i.ql){
      cntcnt[cnt[a[l]]]--;
      cnt[a[l]]--;
      cntcnt[cnt[a[l]]]++;
      if(cntcnt[showmax]==0) showmax--;
      // cout<<'l' _ l _ 'r' _ r _ "showmax" _ showmax<<'\n';
      l++;
    }
    while(r>i.qr){
      cntcnt[cnt[a[r]]]--;
      cnt[a[r]]--;
      cntcnt[cnt[a[r]]]++;
      if(cntcnt[showmax]==0) showmax--;
      r--;
    }
    ans[i.id]=showmax;
  }
  for(ll i=0;i<Q;i++) cout<<ans[i]<<'\n';
}
int main() {
  fastio
  init();
  solve();
  return 0;
}

:::
## 練習題
* CF 136B Little Elephant and Array
* CF 86D Powerful Array
* CF 877F Ann and Books
* CF 617E XOR and Favorite Number
* CF 101138D Strange Queries (難)
* TIOJ 1699 害蟲決戰時刻
* TIOJ 1694 你的重生之旅
* ABC 242G Range Pairing Query
* ABC 238G Cubic?
# CDQ 分治
#### 起源
* 2008 年由中國 IOI 選手陳丹琦整理、總結
* 原文連結:
https://www.cs.princeton.edu/~danqic/papers/divide-and-conquer.pdf
* CDQ = 陳丹琦
* CDQ 分治是從 Merge Sort 的概念延伸出來的，解決問題的方法
* 具體可以解決哪些類型的問題不好總結，接下來就知道了 > <
# 二維偏序
* 接下來要介紹的是偏序問題，偏序問題的解法蘊含 CDQ 分治的核心思想
* 逆序數對是一種偏序問題，如果你寫過逆序數對 (用 Merge Sort 做)，你基本上已經會 CDQ 分治了
## 名詞定義
* 序 = 集合裡面兩個東西之間的大小、順序關係
* 例如整數集合中，「1 < 2」、「3 < 4」
* 全序:任兩個東西之間一定可以互相比較
* 偏序:任兩個東西之間不一定可以互相比較

## 例題一. 二維偏序問題
* 有 $N$ 個數對，對於第 i 個數對 $(x_i, y_i)$，計算有多少個數對 $(x_k, y_k)$ 滿足 $x_k < x_i$ 且 $y_k < y_i$。
* (假設所有 xi 相異、所有 yi 相異)

## 實作流程
:::success
* 先把所有數對按照 $x$ 座標排序
---
* 接著想辦法算答案，也就是對每個 $(x_i, y_i)$ 計算有多少個 $(x_k, y_k)$ 滿足條件，你會發現滿足條件的 $k$ 一定在 $i$ 的前面 (因為按照 $x$ 座標排序)
* 從序列中間砍一半，$k$、 $i$ 可以分成三種情況
-- $k$ 在左邊，$i$ 在左邊
-- $k$ 在右邊，$i$ 在右邊
-- $k$ 在左邊，$i$ 在右邊
* 套用分治，前兩種情況可以遞迴解決
* 現在要處理第三種情況
----
* 現在要處理 $k$ 在左邊，，$i$ 在右邊的情況
* 重要觀察:左邊的所有 $x$ 座標都比右邊的小
* 計算 $k$ 在左邊，$i$ 在右邊的情況時，可以忽視 $x$ 座標!
* 現在把左右兩半邊都按照 $y$ 座標排序
* 接著枚舉右邊的每個數對 $i，，計算左邊有多少數對 $k$ 滿足條件
* 當枚舉 $i$ 的指針往右移動時，滿足條件的 $k$ 不會變少
* 雙指針把算到 $k$ 的數量累加在 $i$ 的答案
---
Question: 那要怎麼對y排序呢?
* 「把點按照 y 排序」那邊如果是用一般的 sort 排序，總
時間複雜度會是 $O(nlog^2n)$
* 但其實這可以套用 Merge Sort 的框架，對 y 座標
Merge Sort，總時間複雜度可以降為 $O(n log n)$
:::
## 實作方法
:::success

#define eb emplace_back

struct info{
    ll x,y,id;//id是數對在原本陣列的位置
}

ll N;
vector<info> v;
vector<ll> ans;

void init(){
    cin>>N;
    v.clear();v.resize(N);
    ans.resize(N);
    
    ll cnt=0;
    for(auto& i:v){
        cin>>i.x>>i.y;
        i.id=cnt++;
    }
}

void cdq(ll L,ll R){
    if(L==R) return;
    
    ll mid=(L+R)/2;
    cdq(L,mid),cdq(mid+1,R);
    
    vector<info> temp;//存暫時排序的值
    ll lptr=L,rptr=mid+1;
    
    while(lptr<=mid && rptr<=R){
        if(v[lptr].y<v[rptr].y)    temp.eb(v[lptr++]);
        else{
            temp.eb(v[rptr]);
            ans[v[rptr].id]+=(lptr-L);
            rptr++;
        }
    }
    
    while(lptr<=mid)    temp.eb(v[lptr++]);
    while(rptr<=R){
        temp.eb(v[rptr]);
        ans[v[rptr].id]+=(lptr-L);
        rptr++;
    }
    
    for(ll pt=0,pv=L;pv<=R;pt++,pv++){
        v[pt]=temp[pv]
    }
}

int main(){
    init();
    sort(v.begin(),v.end(),
         [&](const info& a,const info& b){
       return a.x<b.x; 
    });
    cdq(0,N-1);
    return 0;
}

:::
# 三維偏序
* 有 $N$ 個數對，對於第 $i$ 個數對 $(x_i, y_i, z_i)$，計算有多少個數對 $(x_k, y_k, z_k)$ 滿足 $x_k < x_i$ 且 $y_k < y_i$且 $z_k < z_i$。
* (假設所有 $x_i$ 相異、所有 $y_i$ 相異、所有 $z_i$ 相異)
## 實作流程
:::success
* 解法其實是二維偏序的延伸，一樣先對 x 排序、對 y 套 Merge Sort。
* 在做雙指針的時候,我們已經考慮完了 x， y 兩個維度，想看剩下的 z 座標該怎麼處理?

1. 老樣子，先按照 $x$ 排序，這樣就解決掉 $x$ 這個維度了
2. 接著對 $y$ 套 Merge Sort，假設已經進行到最後一步合併
3. 現在目標:枚舉右邊的數對 $i$，計算左邊有多少數對 $k$ 滿足條件$y$ 這個維度一樣用 Merge Sort 的雙指針解決，那 $z$ 呢?
4. 很簡單，資料結構就行了!

* 目標:枚舉右邊的數對 $i$,計算左邊有多少數對 $k$ 滿足條件
* 相較於二維偏序，需要多一項工具幫我們處理第三個維度:值域資料結構 (BIT / 線段樹)
* 值域資結用來維護「數字的累計次數」
* 考慮 Merge Sort 過程中，接下來該放進新陣列的東西
* 如果是要放左半邊的東西，那就單點加值，把 $z_k$ 的次數 $+1$
* 如果是要放右半邊的東西，那就詢問 $1 ∼ z_i − 1$ 的次數總和
* 次數總和即是 對 $i$ 而言，左半邊有多少數對 $k$ 滿足 $x, y, z$ 三個維度都小於 $i$ ，正是我們要算的!
:::
## 實作方法
:::success

#define eb emplace_back

struct info{
    ll x,y,z,id;//id是數對在原本陣列的位置
}

ll N;
vector<info> v;
vector<ll> ans;

void init(){
    cin>>N;
    v.clear();v.resize(N);
    ans.resize(N);
    
    ll cnt=0;
    for(auto& i:v){
        cin>>i.x>>i.y>>i.z;
        i.id=cnt++;
    }
}

void cdq(ll L,ll R){
    if(L==R) return;
    
    ll mid=(L+R)/2;
    cdq(L,mid),cdq(mid+1,R);
    
    vector<info> temp;//存暫時排序的值
    ll lptr=L,rptr=mid+1;
    //初始化BIT
    
    while(lptr<=mid && rptr<=R){
        if(v[lptr].y<v[rptr].y){
            temp.eb(v[lptr]);
            BIT.upd(v[lptr].z,1);
            lptr++;
        }
        else{
            temp.eb(v[rptr]);
            ans[v[rptr].id]+=BIT.qry(v[rptr].z-1);
            rptr++;
        }
    }
    
    while(lptr<=mid){
        temp.eb(v[lptr]);
        BIT.upd(v[lptr].z,1);
        lptr++;
    }
    while(rptr<=R){
        temp.eb(v[rptr]);
        ans[v[rptr].id]+=BIT.qry(v[rptr].z-1);
        rptr++;
    }
    
    for(ll pt=0,pv=L;pv<=R;pt++,pv++){
        v[pt]=temp[pv]
    }
}

int main(){
    init();
    sort(v.begin(),v.end(),
         [&](const info& a,const info& b){
       return a.x<b.x; 
    });
    cdq(0,N-1);
    return 0;
}

:::
## 實作優化
:::danger
* 上面的 code 其實效率很差
* 瓶頸在於「初始化 BIT」，如果每次都要重新掃過整個 BIT 初始成 0，那這樣會 TLE
* 解決方法很簡單，只要記錄你在 BIT 做的操作，在 cdq() 函式結尾撤銷這些操作就好。
* 這樣時間複雜度就好很多，等等會分析具體複雜度是多少。

#define eb emplace_back
#define mkp make_pair

struct info{
    ll x,y,z,id;//id是數對在原本陣列的位置
}

ll N;
vector<info> v;
vector<ll> ans;

void init(){
    cin>>N;
    v.clear();v.resize(N);
    ans.resize(N);
    
    ll cnt=0;
    for(auto& i:v){
        cin>>i.x>>i.y>>i.z;
        i.id=cnt++;
    }
}

void cdq(ll L,ll R){
    if(L==R) return;
    
    ll mid=(L+R)/2;
    cdq(L,mid),cdq(mid+1,R);
    
    vector<info> temp;//存暫時排序的值
    vector<pll> BIT_op;
    ll lptr=L,rptr=mid+1;
    //初始化BIT
    
    while(lptr<=mid && rptr<=R){
        if(v[lptr].y<v[rptr].y){
            temp.eb(v[lptr]);
            BIT.upd(v[lptr].z,1);
            BIT_op.eb(mkp(v[lptr].z,1));
            lptr++;
        }
        else{
            temp.eb(v[rptr]);
            ans[v[rptr].id]+=BIT.qry(v[rptr].z-1);
            rptr++;
        }
    }
    
    while(lptr<=mid){
        temp.eb(v[lptr]);
        
        //小小常數優化:這兩行不需要 
        //想想看Merge Sort的過程就可以知道為什麼
        //(答案不改變阿)
        //BIT.upd(v[pl].z,1);
        //BIT_op.ebk(mkp(v[pl].z,1));
        lptr++;
    }
    while(rptr<=R){
        temp.eb(v[rptr]);
        ans[v[rptr].id]+=BIT.qry(v[rptr].z-1);
        rptr++;
    }
    
    for(ll pt=0,pv=L;pv<=R;pt++,pv++){
        v[pt]=temp[pv]
    }
    
    //撤銷所有操作,讓BIT變回初始狀態
    for(auto& op:BIT_op){
        BIT.upd(op.first,-op.second);//區間加值
    }
}

int main(){
    init();
    sort(v.begin(),v.end(),
         [&](const info& a,const info& b){
       return a.x<b.x; 
    });
    cdq(0,N-1);
    return 0;
}

* Merge Sort 的複雜度:$O(n log n)$
* 操作一次 BIT 的複雜度:$O(log C)$,$C$ 是值域
* 總時間複雜度:$O(n log n log C)$
* 把所有維度先離散化的話，複雜度會變為 $O(n log^2n)$
:::
## 三維偏序—變形
### 第一種:< 變 >
非常簡單:
1. x 座標:由大到小排序
2. y 座標:對 y Merge Sort 時，就改成由大排到小
3. z 座標:值域 BIT / 線段樹，前綴詢問改成後綴

另解
* 把x,y,z乘上(-1)，其餘code跟<相同

### 第二種:< 變 ≤
一樣很簡單，解決方式:
1. x 座標:維持一樣的方法
2. y 座標:對 y Merge Sort 時，合併時先放左邊的條件:if (左 < 右) 改成 if (左 $\leq$ 右)
3. z 座標:值域 BIT / 線段樹簡單改一下詢問區間就好

## 第三種:一樣是 <,只是一個維度會有相同數字出現
這個比較麻煩一點，解決方式:
1. 首先,先==把長得一模一樣的數對綁在一起==
2. x 座標:==x 小的在前，如果 x 相同那 y 大的在前,如果還是相同那 z 大的在前==
3. y 座標:對 y Merge Sort 時，合併時先放左邊的條件一定要是 if (左 < 右)，確保 y 相同的時候，會是右邊先被放入
4. z 座標:維持一樣的方法
## 模板測試
* 嚴格偏序:CF 101485G
* 非嚴格偏序:洛谷 P3810 三维偏序模板題

## 偏序問題的啟發
* 剛剛偏序問題的解法其實就是 CDQ 分治的一種
* CDQ 分治的核心:利用 Merge Sort 的合併過程，製造單調性,從而降低需要考慮的維度
* 三維偏序的解法中:
-- 處理 x 這個維度的手段:一開始的排序
-- 處理 y 這個維度的手段:Merge Sort 的單調性 (雙指針)
-- 處理 z 這個維度的手段:BIT / 線段樹
* 如果不用 CDQ 的話，你會需要寫二維動態開點資料結構，實作繁雜常數又大
* 以剛才的例題，我們會說這是「對 x 分治，對 y 合併排序」
* 對誰分治、對誰合併排序，你可以任意選擇，選實作方便的就好
* 高維度的偏序一樣可以用 CDQ，只不過要嵌套，也就是 CDQ 套 CDQ
* 參考這篇四維偏序的教學:https://www.cnblogs.com/mlystdcall/p/6232324.html,寫得非常好懂，因為上課時間有限所以暫時不細講
* 一層 CDQ 可以幫你壓掉一個維度
* $k$ 維偏序需要壓掉 $k − 1$ 層維度，所以要套 $k − 1$ 層 CDQ時間複雜度會是 $O(n log^{k−1}n)$
* 其實你不一定要用 CDQ，你也可以寫$k − 1$ 維資料結構之類的，常數什麼的自己想辦法 OwO

# 操作分治