主题

主题

 
   

stars

原题:http://acm.hdu.edu.cn/showproblem.php?pid=5126

Problem Description

John loves to see the sky. A day has Q times. Each time John will find a new star in the sky, or he wants to know how many stars between (x1,y1,z1) and (x2,y2,z2).

Input

The first line contains a single integer T(1≤T≤10) (the data for Q>100 less than 6 cases),, indicating the number of test cases.

The first line contains an integer Q(1≤Q≤50000),indicating how many times in a day.

Next Q lines contain some integers, first input an integer A(1≤A≤2).If A=1 then input 3 integers x, y and z, indicating a coordinate of one star.. If A=2 then input 6 integers x1,y1,z1,x2,y2,z2(1≤x,y,z,x1,y1,z1,x2,y2,z2≤109,x1≤x2,y1≤y2,z1≤z2).

Output

For each “A=2”,output an integer means how many stars in such a section.

Sample Input

2

11

1 1 1 1

2 1 1 1 1 1 1

1 2 2 2

1 1 1 2

2 1 1 1 2 2 2

1 3 3 3

1 4 4 4

1 5 5 5

1 6 6 6

2 1 1 1 6 6 6

2 3 3 3 6 6 6

11

1 1 1 1

2 1 1 1 1 1 1

1 2 2 2

1 1 1 2

2 1 1 1 2 2 2

1 3 3 3

1 4 4 4

1 5 5 5

1 6 6 6

2 1 1 1 6 6 6

2 3 3 3 6 6 6

Sample Output

1

3

7

4

1

3

7

4


题目大意:

在一个三维空间中,给出n个操作:

  1. 在(x,y,z)插入一个点

  2. 查询方体(x1,y1,z1)-(x2,y2,z2)中点的个数


个人解法:

ctbb给32MB的树套树套树

长知识了。CDQ是可以套CDQ了。记得曾经谁说过,某知名选手(也许就是CDQ吧)基于此提出了十分优秀的算法,在O(nlog^kn)的时间内处理k维偏序问题。

现在大概明白了此算法。

首先如果是一个二维平面,拿一个CDQ分治套一个树状数组可以轻易解决。

现在拓展到了三维,关键是如何降维。

大致是这样的

CDQ1(l1,r1){

  CDQ1(l1,m1); CDQ1(m1+1,r1);

  上来两个按照x排序好的数组A1[l1,m1],A1[m1+1,r1]

  接下来要做的事情就是统计左边的修改对右边查询的影响

  我们把左边的修改(注意不加右边的修改)与右边的查询(注意不加左边的查询)放到一起,按照x排序(就是归并一次)。不加那两个玩意是因为已经计算过贡献了,得到A2[l2,r2]

  CDQ2(l2,r2)

}

CDQ2(l2,r2){

  现在我们发现里面所有的点都是可以有贡献的,那么相当于现在的时间就是x,变为了两维坐标(y,z)了

  然后就做普通的事情。

  CDQ(l2,m2); CDQ(m2+1,r2);

  上来两个按照y排好序的数组A2[l2,m2],A2[m2+1,r2]

  然后扫一扫就可以了

}

发现这个问题是具有子问题性的,我们还可以继续分治下去。这样就可以处理k维了。而且代码十分相似。

注意到k维的话,其实我们的时间复杂度带了一个2的常数。也就是说,实际上k维问题的时间复杂度是O(n*2^(k-1)*loog^k),空间复杂度为O(k*n)。


需要注意的,在交接的地方:

从1进入到2的时候,需要:

  1. A2的num为该进去的元素(左边的操作右边的询问)按照y排序的编号。从CDQ1(l,r)的l开始编号。

  2. 在把元素给A2的时候要把A2的ans重新赋值为0。

  3. 用一个数组input1记录A1这个对应的A2的num。

  4. 可以同样按照第一层的Ans一样,通过Ans2[Num[i]]=A2[i].ans。

  5. 在计算完之后把Ans2[i]清零与input1清零。

由于样例的不可调试性(不行您可以去尝试调试这个样例),我为此做了一个上午……模板的实现总是那么艰难。

但是现在会打之后,也许就是一个熟练的过程了吧……到考场上如果需要打树套树套树,我还是愿意尝试CDQ+CDQ+树状数组的……

2013年集训队第二次集训队作业有一个一模一样的题目……可以尝试一下……不过那道题似乎空间不是那么死,可以尝试CDQ+树套树,当然也可以尝试CDQ+CDQ+CDQ(但是CDQ的代码比BIT的长,所以末维支持BIT)……


代码如下:

https://code.csdn.net/snippets/2283048

 
 
评论