從二維數點（二維偏序）到三維偏序。

用 cdq 分治可以解決二維數點問題。

1.洛谷 P1908 逆序對

題意

求所有數對 $(i,j)$ 的個數，滿足 $i<j$ 且 $a_i>a_j$。

$1\le n\le 5\times 10^5$。

思路

欲學習樹狀數組解法的，請移步這里。這里用 cdq 分治的作為復習。

在很久很久以前，我們介紹過歸并排序，說到可以使用歸并排序的思想來解決這樣的逆序對（二維偏序、二維數點）問題，也可以用于找一些特定的數對。

cdq 分治是一種思想，體現的當然是“分而治之”。處理區間 $(l,r)$，其流程大概為：

• 找到中點 $mid$。
• 將所有可能存在的點對分為三類：
  1 . $i\in [l,mid],j\in [l,mid]$；
  2 . $i\in [l,mid],j\in [mid+1,r]$;
  3 . $i\in [mid+1,r],j\in [mid+1,r]$。
• 遞歸處理第 $1,3$ 類；
• 設法處理第 $2$ 類。

（以上參考自OI - WIKI）

嚴格來說，這種二維偏序題并不能算作 cdq 分治，其實只是分治思想和雙指針的應用。我們考慮雙指針 $p\in [l,mid]$ 與 $q\in [mid+1,r]$：

• 如果 $a_p\le a_q$，那么當前 $p$ 并不能對 $q$ 產生貢獻，我們考慮將 $p$ 合并到新數組 $b$ 去；
• 否則即 $a_p>a_q$，因為 $p<q$ 所以此時產生了逆序對，可以產生貢獻；
• 因為我們已經分治處理了 $l～mid$ 和 $mid+1～r$，所以以 $mid$ 分開的左右兩段區間都已經是有序的了（上一步的合并操作），所以 $a_q$ 比 $l～p?1$ 的都要大，比 $p～mid$ 的都要小，所以逆序對個數增加 $mid?p+1$ 個；
• 那么 $a_q$ 已經不能產生接下來的逆序對，扔進 $b$。

記得把已經排序好了的 $b$ 數組復制到 $a_{l～r}$ 去：

void cdq(ll l,ll r)
{if(l>=r)return;ll mid=(l+r)>>1;cdq(l,mid);cdq(mid+1,r);ll i=l,p=l,q=mid+1;while(p<=mid&&q<=r){if(q>r||p<=mid&&a[p]<=a[q])b[i++]=a[p++];//并入沒法貢獻的p else {b[i++]=a[q++];cnt+=mid-p+1;//a(i)>a(j)的數量，取右邊大的 }}while(p<=mid)b[i++]=a[p++];while(q<=r)cnt+=mid-p+1,b[i++]=a[q++];for(int o=l;o<=r;o++)a[o]=b[o];
}

代碼

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5e5+9;
ll n,a[N];
ll b[N],cnt;
void cdq(ll l,ll r)
{if(l>=r)return;ll mid=(l+r)>>1;cdq(l,mid);cdq(mid+1,r);ll i=l,p=l,q=mid+1;while(p<=mid&&q<=r){if(q>r||p<=mid&&a[p]<=a[q])b[i++]=a[p++];//并入沒法貢獻的p else {b[i++]=a[q++];cnt+=mid-p+1;//a(i)>a(j)的數量，取右邊大的 }}while(p<=mid)b[i++]=a[p++];while(q<=r)cnt+=mid-p+1,b[i++]=a[q++];for(int o=l;o<=r;o++)a[o]=b[o];
}
int main()
{scanf("%lld",&n);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);cdq(1,n);printf("%lld",cnt);return 0;
}

2.洛谷 P2717 寒假作業/P2804 神秘數字

題意

給定一個長度為 $n$ 的正整數序列 $a_i$，求出有多少個連續子序列的平均值不小于 $k$。

$1\le n\le 10^5$，$1\le ?a_i,k\le 10^4$。

洛谷 P2804：要求平均值嚴格大于 $k$。

這里按照洛谷 P2717 的題面進行講解。

思路

在這里我們講到，這是一個“順序對”：求所有 $l<r,s_l\le s_r$ 的個數，我們只要取比 $a_q$ 小的左邊：$l～p?1$即可，每次貢獻加 $p?l$。

因為是前綴和數組，所以 $l=0$ 是合法的，記得從 $0$ 開始。

代碼 1 - 寒假作業

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5+9;
ll n,k,a[N];
ll s[N],cnt,b[N];
void cdq(ll l,ll r) 
{if(l>=r)return;ll mid=(l+r)>>1;cdq(l,mid);cdq(mid+1,r);ll i=l,p=l,q=mid+1;while(p<=mid&&q<=r){if(s[p]<=s[q])b[i++]=s[p++];else {cnt+=p-l;//s(i)<s(j)，取左邊小的 b[i++]=s[q++];}}while(p<=mid)b[i++]=s[p++];while(q<=r)cnt+=p-l,b[i++]=s[q++];for(ll o=l;o<=r;o++)s[o]=b[o];
}
int main()
{scanf("%lld%lld",&n,&k);for(ll i=1;i<=n;i++){scanf("%lld",&a[i]);a[i]-=k;s[i]=s[i-1]+a[i];}cdq(0,n);printf("%lld",cnt);return 0;
}

第 $2$ 題，要求嚴格大于，所以只需要改成：

if(s[p]<s[q])b[i++]=s[p++];

即可。記得取題目規定的模。

3.洛谷 P2163 SHOI2007 園丁的煩惱

4.洛谷 P3157 CQOI2011 動態逆序對/UVA11990 "Dynamic’’ Inversion