P3810 【模板】三維偏序（陌上花開）
更好的閱讀體驗1
更好的閱讀體驗2
前置演算法
- 樹狀陣列求逆序對
- 歸并排序求逆序對
解題之前，讓我們來看一看榷訓版本 \(\to\) 二維偏序
題意
給定兩個長度為陣列 \(a_1,a_2,\dots,a_n\)，\(b_1,b_2,\dots,b_n\) 求對于每一個 \(i\)，\(a_j\le a_i\) 且 \(b_j\le b_i\) 的 \(j\) 有多少個，
解法1
考慮用結構體把陣列存起來，對 \(a\) 進行排序，再用一個值域樹狀陣列維護 \(b\) 值即可，
還沒完，由于可能出現 \(a_i=a_j\) 且 \(b_i=b_j\) 的情況，所以需要去重，
提到去重，就要在結構體里面多加一個 \(x\) ， \(x_i\) 表示與 \(a_j=a_i,b_j=b_i\) 的 \(j\) 的個數，\(x_i\) 初始為 \(1\)
去重毒瘤的要死
解法2
還是用結構體存，對 \(a\) 進行排序+去重，后面考慮用歸并排序來求
回想一下歸并排序求逆序對，我們求的是 \(a_i\) 作為逆序對 \((j,i)\) 的 \(j\) 的總個數，
在這里，\(a\) 已經按大小排好了，所以我們只考慮對 \(b\) 值求逆序對就行了，
深刻注意解法2
三維偏序
第一步
和二維偏序一樣，先按 \(a\) 值排好序，去重
第二步
為了簡化題目，先考慮簡易版本不存在 \(a_i=a_j\) 且 \(b_i=b_j\) 且 \(c_i=c_j\) 的情況，標準版本放在第三步，
進入到今天的正題： CDQ 講解部分，
CDQ 分治，顧名思義，是一種分治，而分治，就需要把 \([l,r]\) 分為 \([l,mid]\) 和 \([mid+1,r]\) ，而對于我們要尋找的一個符合 \(a_j\le a_i,b_j\le b_i,c_j\le c_i\) 的點對 \((i,j)\) 必須符合以下三種情況之一：
- \(1\le i,j\le mid\gets\) 這在遞回處理左半邊時已經處理了
- \(mid\lt i,j\le n\gets\) 這在遞回處理右半邊時已經處理了
- \(1\le i,j\le n\gets\) 這是我們在遞回之后需要處理的點對
按分治三部曲走，接下來就是合并左右區間并統計答案了了，這里按歸并排序求逆序對的思路來，
由于 \(a,b\) 值都被我們處理好了，接下來就是毒瘤的 \(c\) 值，用樹狀陣列維護，
在合并中，我們分兩種情況：
- 此時的最小值在左，那么我們讓樹狀陣列的左邊那個數的 \(c\) 值位置加一
- 此時的最小值在右，那么我們讓答案加上樹狀陣列從 \(1\) 到右邊數的 \(c\) 值位置的和
如果搞不懂為什么左是加，右是查，建議重新看一看歸并排序求逆序對，
注意：每一次使用完后樹狀陣列要清空，如果單純 memset，會超時（因為是 \(O(n)\) ），清空應該對于每一個被存放在樹狀陣列里的 \(c_i\) ，其在樹狀陣列里面的值 \(-1\)
int tmp[maxn]; // 臨時存放合并好的值的陣列
void CDQ(int l,int r){
if(l == r) return;
int mid = l + r >> 1,p = l,q = mid + 1,len = 0;
CDQ(l,mid),CDQ(mid + 1,r); // 遞回處理
while(p <= mid && q <= r){ // 合并子區間
if(a[p].b <= a[q].b) bit.update(a[p].c,1),tmp[++len] = a[p++]; // 選左邊，此時更新樹狀陣列
else a[q].ans += bit.query(a[q].c),tmp[++len] = a[q++]; // 選右邊，此時答案要加上值域樹狀陣列的查詢
}
while(p <= mid) bit.update(a[p].c,1),tmp[++len] = a[p++]; // 歸并左邊剩下部分
while(q <= r) a[q].ans += bit.query(a[q].c),tmp[++len] = a[q++]; // 歸并右邊剩下部分
for(int i = l;i <= mid;++i) bit.update(a[i].c,-1); // 清空
for(int i = 1;i <= len;++i) a[l + i - 1] = tmp[i]; // 把臨時陣列里的值拷貝到原陣列
}
第三步
由于第二步只能處理不存在相同的情況，接下來講解如果存在 \(a_i=a_j,b_i=b_j,c_i=c_j\) 的 \((i,j)\) 該怎么處理，
注意剛才我們樹狀陣列是這樣更新的：bit.update(a[p].c,1)
這里的 1 實際上就是 \(a_s=a_p,b_s=b_p,c_s=c_p\) 的 \(s\) 的個數，記為 \(x\) ，\(x_i\) 我們在去重時求出，
因此代碼如下：
int tmp[maxn];
void CDQ(int l,int r){
if(l == r) return;
int mid = l + r >> 1,p = l,q = mid + 1,len = 0;
CDQ(l,mid),CDQ(mid + 1,r);
while(p <= mid && q <= r){
if(a[p].b <= a[q].b) bit.update(a[p].c,a[p].x),tmp[++len] = a[p++];
else a[q].ans += bit.query(a[q].c),tmp[++len] = a[q++];
}
while(p <= mid) bit.update(a[p].c,a[p].x),tmp[++len] = a[p++];
while(q <= r) a[q].ans += bit.query(a[q].c),tmp[++len] = a[q++];
for(int i = l;i <= mid;++i) bit.update(a[i].c,-a[i].x);
for(int i = 1;i <= len;++i) a[l + i - 1] = tmp[i];
}
第四步
這時 CDQ 分治已經完成了，我們現在需要統計答案
按照剛才的代碼，a[i].ans 表示 \(a_j\le a_i,b_j\le b_i,c_j\le c_i\) 但不包括 \(a_j=a_i,b_j=b_i,c_j=c_i\) 的 \(j\) 的個數，而 a[i].x 正好表示了 \(a_j=a_i,b_j=b_i,c_j=c_i\) 的 \(j\) 的個數，于是 a[i].ans + a[i].x 就是去重后第 \(i\) 個點的答案，
for(int i = 1;i <= cnt;++i) res[a[i].ans + a[i].x - 1] += a[i].x; // 注意是 + a[i].x，因為還有與 i 值相同所有 j，其總個數是 a[i].x
for(int i = 0;i < n;++i) printf("%d\n",res[i]);
\(\color{#52C41A}\texttt{AC CODE}\)
#include<stdio.h>
#include<algorithm>
const int maxn = 114514;
int n,k;
struct BIT{
int t[maxn << 1];
int lowbit(int i){return i & -i;}
void update(int i,int x){for(;i <= k;i += lowbit(i)) t[i] += x;}
int query(int i){int ans = 0;for(;i;i -= lowbit(i)) ans += t[i];return ans;}
} bit; // 樹狀陣列
struct number{
int a,b,c,ans,x;
bool operator<(const number& y) const{return a != y.a ? a < y.a : b != y.b ? b < y.b : c < y.c;}
} a[maxn],tmp[maxn]; // 數的結構體
int res[maxn];
void CDQ(int l,int r){
if(l == r) return;
int mid = l + r >> 1,p = l,q = mid + 1,len = 0;
CDQ(l,mid),CDQ(mid + 1,r);
while(p <= mid && q <= r){
if(a[p].b <= a[q].b) bit.update(a[p].c,a[p].x),tmp[++len] = a[p++];
else a[q].ans += bit.query(a[q].c),tmp[++len] = a[q++];
}
while(p <= mid) bit.update(a[p].c,a[p].x),tmp[++len] = a[p++];
while(q <= r) a[q].ans += bit.query(a[q].c),tmp[++len] = a[q++];
for(int i = l;i <= mid;++i) bit.update(a[i].c,-a[i].x);
for(int i = 1;i <= len;++i) a[l + i - 1] = tmp[i];
}
int main(){
scanf("%d%d",&n,&k);
for(int i = 1;i <= n;++i) scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c),a[i].x = 1,a[i].ans = 0;
std::sort(a + 1,a + n + 1); // 排序
int cnt = 1;
for(int i = 2;i <= n;++i)
if(a[i].a == a[cnt].a && a[i].b == a[cnt].b && a[i].c == a[cnt].c) ++a[cnt].x; // 如果遇到與 i 一樣的，x 值就要自加一
else a[++cnt] = a[i];
CDQ(1,cnt); // 注意不是 CDQ(1,n)
for(int i = 1;i <= cnt;++i) res[a[i].ans + a[i].x - 1] += a[i].x;
for(int i = 0;i < n;++i) printf("%d\n",res[i]);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/287060.html
標籤：其他
上一篇：PHP中操作資料庫的預處理陳述句