BZOJ 3262: 陌上花開 CDQ三維偏序，樹套樹，兩種解法

2019-11-08 02:29:56

字體：大中小

來源：轉載

供稿：網友

Description 有n朵花，每朵花有三個屬性：花形(s)、顏色(c)、氣味(m)，又三個整數表示。現要對每朵花評級，一朵花的級別是它擁有的美麗能超過的花的數量。定義一朵花A比另一朵花B要美麗，當且僅當Sa>=Sb,Ca>=Cb,Ma>=Mb。顯然，兩朵花可能有同樣的屬性。需要統計出評出每個等級的花的數量。 Input 第一行為N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分別表示花的數量和最大屬性值。以下N行，每行三個整數si, ci, mi (1 <= si, ci, mi <= K)，表示第i朵花的屬性 Output 包含N行，分別表示評級為0…N-1的每級花的數量。 Sample Input 10 3

3 3 3

2 3 3

2 3 1

3 1 1

3 1 2

1 3 1

1 1 2

1 2 2

1 3 2

1 2 1

Sample Output 3

HINT

1 <= N <= 100,000, 1 <= K <= 200,000

解題方法：三維。。。第一維排序，第二維樹狀數組，第三維treap。復雜度: O(n*logn*logn)

//bzoj 3262//1維排序，二維BIT，3維平衡樹#include <bits/stdc++.h>using namespace std;int n, m, tmp, root[200005], cnt[200005], ans[200005];struct node{ int a, b, c; node(){} node(int a, int b, int c) : a(a), b(b), c(c) {} bool Operator < (const node &rhs) const{ if(a == rhs.a && b == rhs.b) return c < rhs.c; if(a == rhs.a) return b < rhs.b; return a < rhs.a; }} a[200005];namespace multi_treap{ struct data{ int l, r, v, size, rnd, w; }tree[5000005]; int size; void update(int k) { tree[k].size = tree[tree[k].l].size + tree[tree[k].r].size + tree[k].w; } void rturn(int &k) { int t = tree[k].l; tree[k].l = tree[t].r; tree[t].r = k; tree[t].size = tree[k].size; update(k); k = t; } void lturn(int &k) { int t = tree[k].r; tree[k].r = tree[t].l; tree[t].l = k; tree[t].size = tree[k].size; update(k); k=t; } void insert(int &k, int x) { if(k == 0) { size++; k = size; tree[k].size = tree[k].w = 1; tree[k].v = x; tree[k].rnd = rand(); return ; } tree[k].size++; if(tree[k].v==x) tree[k].w++;//每個結點順便記錄下與該節點相同值的數的個數 else if(x > tree[k].v) { insert(tree[k].r, x); if(tree[tree[k].r].rnd < tree[k].rnd) lturn(k);//維護堆性質 } else { insert(tree[k].l, x); if(tree[tree[k].l].rnd < tree[k].rnd) rturn(k); } } void del(int &k,int x) { if(k == 0)return; if(tree[k].v == x) { if(tree[k].w > 1) { tree[k].w--; tree[k].size--; return;//若不止相同值的個數有多個，刪去一個 } if(tree[k].l * tree[k].r == 0)k = tree[k].l + tree[k].r;//有一個兒子為空 else if(tree[tree[k].l].rnd < tree[tree[k].r].rnd) rturn(k),del(k,x); else lturn(k),del(k,x); } else if(x > tree[k].v) tree[k].size--, del(tree[k].r,x); else tree[k].size--, del(tree[k].l,x); } void query_rank(int k, int num){ if(!k) return ; if(num == tree[k].v){tmp += tree[tree[k].l].size + tree[k].w; return;} else if(num < tree[k].v) query_rank(tree[k].l, num); else{tmp += tree[tree[k].l].size + tree[k].w; query_rank(tree[k].r, num);} }}using namespace multi_treap;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)) insert(root[i], y);} inline void query(int x, int y) {for(int i = x; i; i -= lowbit(i)) query_rank(root[i], y);}}using namespace BIT;int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].c); sort(a + 1, a + n + 1); for(int i = 1; i <= n; i++){ if(a[i].a == a[i+1].a && a[i].b == a[i+1].b && a[i].c == a[i+1].c && i!=n){ cnt[i+1] += cnt[i]+1; } else{ tmp = 0; query(a[i].b, a[i].c); ans[tmp] += cnt[i] + 1; } update(a[i].b, a[i].c); } for(int i = 0; i < n; i++) 另外一種方法就是CDQ：維護三維偏序: 第一維排序，第二位CDQ分治，第三維樹狀數組。

首先我們可以把三維都相的合并到一起，一塊計算。

我們按照s排序，然后依次把他們賦值為1..tot（這里可以把s類比為id）。

接下來按照c排序，開始CDQ分治。

計算左邊對右邊的影響的時候: ①左邊的a都小于右邊 ②在每一邊b也是依次遞增的 ③我們只要掃描右邊，把左邊b小于等于當前的花的花的m加入到樹狀數組，統計目前樹狀數組中m小于等于當前掃描到的花的m的個數就是左邊三維都小于等于當前花得個數。

復雜度: O(n*logn*logn) 但是相對于樹套樹，CDQ的空間復雜度和編程復雜度小的多，運行時間也飛快。

//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;}