CDQ分治
题目链接 : stars
本题是个四维偏序问题:时间,x,y,z。用CDQ分治来解决。而一个CDQ能解决三维偏序问题,四维偏序问题就需要两次CDQ分治。首先第一个CDQ帮助我们解决了 二维 的顺序,还需要再来一个CDQ解决剩下的三维偏序。
首先原序列按照时间已经排好序了,我们需要这样的CDQ分治结构。
//在进入这个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)$
代码:
#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