Loading... CDQ分治 <!--more--> 题目链接 : [stars](http://acm.hdu.edu.cn/showproblem.php?pid=5126) 本题是个四维偏序问题：时间,x,y,z。用CDQ分治来解决。而一个CDQ能解决三维偏序问题，四维偏序问题就需要两次CDQ分治。首先第一个CDQ帮助我们解决了 **二维** 的顺序，还需要再来一个CDQ解决剩下的三维偏序。 首先原序列按照时间已经排好序了，我们需要这样的CDQ分治结构。 ```cpp //在进入这个CDQ2分治前已经保证时间和x是有序的了,即是已经保证了时间和x都是递增的 void CDQ2() { 这里就是一个正常的三维偏序了; 按照y合并; 按照z处理询问; } void CDQ1(int l , int r) { CDQ1(l,mid); CDQ1(mid+1,r); 将左边的修改和右边的询问按照x顺序合并，用于接下来的CDQ2使用; CDQ2(l,r);//这个CDQ用于处理三维偏序，即处理左边的修改和右边的询问 按照x合并; } ``` 时间复杂度为$O(nlog^{3}n)$ 代码: ```cpp #include <bits/stdc++.h> #define eps 1e-6 #define ls (rt << 1) #define rs (rt << 1 | 1) #define lowbit(x) (x & (-x)) #define SZ(v) ((int)(v).size()) #define All(v) (v).begin(), (v).end() #define mp(x, y) make_pair(x, y) #define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> P; const int N = 4e5 + 10; const int M = 1e7 + 10; const int mod = 1e9 + 7; const int inf = 0x3f3f3f3f; const int INF = 2e9; int n, m, ans[N], q[N], Z[N] , c[N]; struct node { int x, y, z, op, id; } star[N], star1[N], star2[N]; void add(int x, int v) { for (; x <= m; x += lowbit(x)) c[x] += v; } int ask(int x) { int res = 0; for (; x > 0; x -= lowbit(x)) res += c[x]; return res; } void cdq2(int l, int r) { if( l >= r) return ; int mid = (l + r) >> 1; cdq2(l,mid); cdq2(mid+1,r); int tot1 = l , i = l; for(int j = mid + 1; j <= r; ++ j) { if(star1[j].op != 0){ while(i <= mid && star1[i].y <= star1[j].y){ if(!star1[i].op) add(star1[i].z , 1); ++ i; } ans[star1[j].id] += star1[j].op * ask(star1[j].z); } } for(int k = l; k < i; ++ k) if(!star1[k].op) add(star1[k].z , -1); /*merge by y*/ i = l; for(int j = mid + 1; j <= r; ++ j) { while(i <= mid && star1[i].y <= star1[j].y){ star2[tot1 ++] = star1[i]; ++ i; } star2[tot1 ++] = star1[j]; } for(;i<=mid; ++i) star2[tot1 ++] = star1[i]; for(int k = l; k <= r; ++ k) star1[k] = star2[k]; } void cdq1(int l, int r) { if (l >= r) return; int mid = (l + r) >> 1; cdq1(l, mid); cdq1(mid + 1, r); int tot1 = 0 , i = l; for(int j = mid + 1; j <= r; ++ j) { if(star[j].op != 0){ while(i <= mid && star[i].x <= star[j].x){ if(!star[i].op) star1[++ tot1] = star[i]; ++ i; } star1[++ tot1] = star[j]; } } cdq2(1, tot1); /*merge by x*/ i = l; tot1 = l; for(int j = mid + 1; j <= r; ++ j) { while(i <= mid && star[i].x <= star[j].x) { star1[tot1 ++] = star[i]; ++ i;} star1[tot1 ++] = star[j]; } for(;i <= mid; ++i) star1[tot1 ++] = star[i]; for(int k = l; k <= r; ++ k) star[k] = star1[k]; } int main() { int T, Q, op, x1, x2, y1, y2, z1, z2; scanf("%d", &T); while (T--) { int tot = 0; m = 0; scanf("%d", &Q); for (int i = 1; i <= Q; ++i) { q[i] = 0; ans[i] = 0; scanf("%d", &op); if (op == 1) { scanf("%d%d%d", &x1, &y1, &z1); Z[++ m] = z1; star[++tot] = node{x1, y1, z1, 0, i}; } else { q[i] = 1; scanf("%d%d%d", &x1, &y1, &z1); scanf("%d%d%d", &x2, &y2, &z2); Z[++ m] = z1 - 1; Z[++ m] = z2; star[++tot] = node{x2, y2, z2, 1, i}; star[++tot] = node{x1 - 1, y1 - 1, z2, 1, i}; star[++tot] = node{x1 - 1, y2, z1 - 1, 1, i}; star[++tot] = node{x2, y1 - 1, z1 - 1, 1, i}; star[++tot] = node{x1 - 1, y2, z2, -1, i}; star[++tot] = node{x2, y1 - 1, z2, -1, i}; star[++tot] = node{x2, y2, z1 - 1, -1, i}; star[++tot] = node{x1 - 1, y1 - 1, z1 - 1, -1, i}; } } sort(Z + 1, Z + m + 1); m = unique(Z + 1, Z + m + 1) - Z - 1; for (int i = 1; i <= tot; ++i){ star[i].z = lower_bound(Z + 1, Z + m + 1, star[i].z) - Z; } cdq1(1, tot); for (int i = 1; i <= Q; ++i) { if (q[i]) printf("%d\n", ans[i]); } } return 0; } cpp Last modification：March 26th, 2020 at 12:41 pm © 允许规范转载 Support 如果觉得我的文章对你有用，请随意赞赏 ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
