HDU5126---stars (CDQ套CDQ套 树状数组)

题意:Q次操作,三维空间内 每个星星对应一个坐标,查询以(x1,y1,z1) (x2,y2,z2)为左下顶点 、右上顶点的立方体内的星星的个数。

注意Q的范围为50000,显然离散化之后用三维BIT会MLE。 我们可以用一次CDQ把三维变成二维,变成二维之后就有很多做法了,树套树,不会树套树的话还可以继续CDQ由二维变成一维,,变成一维了就好做了,,最基本的数据结构题目了。。

不得不说、CDQ真的很神奇。

下面做法就是CDQ套CDQ套树状数组。

 #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = ;
inline int lowbit (int x)
{
return x & -x;
}
int c[maxn*],MAX;
void add(int x,int d)
{
while (x <= MAX)
{
c[x] += d;
x += lowbit(x);
}
}
int sum(int x)
{
int ans = ;
while (x)
{
ans += c[x];
x -= lowbit (x);
}
return ans;
}
struct Point
{
int x,y,z;
int kind,idx,delt;
Point() {}
Point(int _x,int _y,int _z,int _delt,int _kind,int _idx):
x(_x), y(_y), z(_z), delt(_delt), kind(_kind), idx(_idx) {} } star[maxn << ],star3[maxn << ];
int ans[maxn<<];
bool cmp1(const Point &p1,const Point &p2)
{
return p1.x < p2.x || ((p1.x == p2.x) && (p1.idx < p2.idx) );
}
bool cmp2(const Point &p1,const Point &p2)
{
return p1.y < p2.y || ((p1.y == p2.y) && (p1.idx < p2.idx) );
}
void CDQ2(int l,int r)
{
if (l >= r)
return;
int mid = (l + r) >> ;
CDQ2(l,mid);
CDQ2(mid+,r);
int j = l;
for (int i = mid + ; i <= r; i++)
{
if (star3[i].kind == )
{
for ( ; j <= mid && (star3[j].y <= star3[i].y); j++)
{
if (star3[j].kind == )
add(star3[j].z,star3[j].delt);
}
ans[star3[i].idx] += sum(star3[i].z) * star3[i].delt;
}
}
for (int i = l; i < j; i++)
{
if (star3[i].kind == )
add(star3[i].z,-star3[i].delt);
}
inplace_merge(star3+l,star3+mid+,star3+r+,cmp2);
}
void CDQ1(int l,int r)
{
if (l == r)
return;
int mid = (l + r) >> ;
CDQ1(l, mid);
CDQ1(mid+, r);
int tot = ;
for (int j = l; j <= mid ; j++)
if (star[j].kind == )
star3[tot++] = star[j];
for (int i = mid + ; i <= r; i++)
{
if (star[i].kind == )
star3[tot++] = star[i];
}
sort(star3+,star3+tot,cmp1);
CDQ2(,tot-);
}
int vec[maxn << ],idx;
void hash_(int tot)
{
sort(vec,vec+idx);
idx = unique(vec,vec+idx) - vec;
MAX = idx + ;
for (int i = ; i <= tot; i++)
star[i].z = lower_bound(vec,vec+idx,star[i].z) - vec + ;
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif // ONLINE_JUDGE
int T,Q;
scanf ("%d",&T);
while (T--)
{
scanf ("%d",&Q);
int tot = ;
int totq = ;
idx = ;
memset(c,,sizeof (c));
memset(ans,,sizeof(ans));
for (int i = ; i <= Q; i++)
{
int op,x1,y1,z1,x2,y2,z2;
scanf ("%d",&op);
if (op == )
{
scanf ("%d%d%d",&x1,&y1,&z1);
star[tot] = Point(x1,y1,z1,,,totq);
vec[idx++] = z1;
ans[totq] = -;
tot++;
totq++;
}
if (op == )
{
scanf ("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
star[tot] = Point(x1-, y1-, z1-, -, , totq), vec[idx++] = z1-, tot++;
star[tot] = Point(x2, y1-, z1-, , , totq), vec[idx++] = z1-, tot++;
star[tot] = Point(x2 , y2 , z1-, -, , totq), vec[idx++] = z1-, tot++;
star[tot] = Point(x1-, y2, z1-, , , totq), vec[idx++] = z1-, tot++;
star[tot] = Point(x1-, y2, z2 , -, , totq), vec[idx++] = z2 , tot++;
star[tot] = Point(x2 , y2, z2 , , , totq), vec[idx++] = z2 , tot++;
star[tot] = Point(x2 , y1-, z2 , -, , totq), vec[idx++] = z2 , tot++;
star[tot] = Point(x1-, y1-, z2 , , , totq), vec[idx++] = z2 , tot++;
totq++;
}
}
hash_(tot);
CDQ1(,tot-);
for (int i = ; i < totq; i++)
if (~ans[i])
printf("%d\n",ans[i]);
}
return ;
}
上一篇:live555源代码编译


下一篇:Win7 安装 MongoDB