問題背景
在三維坐标系中有n個點,坐标為(xi,yi,zi). 定義一個點A比一個點B小,當且僅當xA<=xB,yA<=yB,zA<=zB。問對于每個點,有多少個點比它小。(n<=1e5)
其實就是離散數學裡的偏序的概念啦,隻不過是到了三維。回顧一下偏序的概念:
偏序關系:自反,反對稱且傳遞,符号<
然後先考慮一下二維偏序吧。可以用最長上升子序列LIS來做,然後我們今天讨論一種特殊分治的做法,這種算法是由08年集訓隊的陳丹琦提出來的,是以叫cdq分治。
主要思想就是先按照第一維排序。然後周遊每一個點,此時我們要統計的就是前面的點中比這個點的y坐标要小的點的個數。我們用一個樹狀數組來維護y坐标這個資訊,于是就隻要得到getsum(y)就行了。
三維的CDQ分治呢,做法如下:
第一維排序,第二維CDQ分治,第三維樹狀數組。
第一維比如先按照x坐标排序。在第二維的CDQ分治時,我們對每一個自區間,先按照y排序,計算左邊對右邊的影響的時候:
- 左邊的x都小于右邊
- 在每一邊y也是依次遞增的
- 我們隻要掃描右邊,把左邊y小于等于目前的y坐标的z坐标更新到樹狀數組,統計目前樹狀數組z坐标小于自己的就是偏序<的點的個數。
複雜度分析
根據主定理:
T(n)=2T(n2)+O(kn)=O(knlogn)T(n)=2T(n2)+O(kn)=O(knlogn)
T(n)=2T(n2)+O(knlogn)=O(knlog2 n)
例題
BZOJ 3262 陌上花開
牛客網的一套題
後面這個題雖然是個裸三維偏序,不過也可以轉化成三個二維偏序。
另附一個BZOJ3262的别人的代碼,可做模闆。
//bzoj 3262
//1維排序,二維分治,3維樹狀數組
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
int n, m, ans[maxn], tree[maxn*4];
struct node{
int a, b, c, s, ans; //s處理相同連續,ans比目前美麗值小個數
node(){}
node(int a, int b, int c, int s, int ans) : a(a), b(b), c(c), s(s), ans(ans) {}
bool operator < (const node &rhs) const{ //按y排序
if(b == rhs.b) return c < rhs.c;
return b < rhs.b;
}
}a[maxn], p[maxn];
bool cmp(node x, node y){ //按照x排序
if(x.a == y.a && x.b == y.b) return x.c < y.c;
if(x.a == y.a) return x.b < y.b;
return x.a < y.a;
}
namespace BIT{
inline int lowbit(int x) {return x&-x;}
inline void update(int x, int y){for(int i = x; i <= m; i+=lowbit(i)) tree[i] += y;}
inline int query(int x){int res = 0; for(int i = x; i; i -= lowbit(i)) res += tree[i]; return res;}
}
using namespace BIT;
void CDQ(int l, int r)
{
if(l == r) return;
int mid = (l + r) >> 1;
CDQ(l, mid);
CDQ(mid+1, r);
sort(p + l, p + mid + 1);
sort(p + mid + 1, p + r + 1);
int i = l, j = mid + 1;
while(j <= r){
while(i <= mid && p[i].b <= p[j].b){
update(p[i].c, p[i].s);
i++;
}
p[j].ans += query(p[j].c);
j++;
}
for(int j = l; j < i; j++) update(p[j].c, -p[j].s);
}
int main(){
int nn;
scanf("%d%d", &nn, &m);
for(int i = 1; i <= nn; i++){
scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].c);
}
sort(a + 1, a + nn + 1, cmp); //按照x排
int cnt = 0; //unique
for(int i = 1; i <= nn; i++){
cnt++;
if(a[i].a != a[i+1].a || a[i].b != a[i+1].b || a[i].c != a[i+1].c){
p[++n] = a[i];
p[n].s = cnt;
cnt = 0;
}
}
CDQ(1, n);
for(int i = 1; i <= n; i++){
ans[p[i].ans + p[i].s - 1] += p[i].s;
}
for(int i = 0; i < nn; i++){
printf("%d\n", ans[i]);
}
return 0;
}
總結
從二維偏序出發,了解了三維偏序的CDQ分治做法。
在這類問題中通常将時間(操作序列)作為第一維,剩下的二維問題使用CDQ分治和資料結構。
這種問題也可以用樹套樹做,據說很煩,樹狀數組套個什麼Treap啥的,總之比這個CDQ要難寫很多。