http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1499. Theresa与数据结构(罗剑桥)
时间限制:2.5s   内存限制:512.0MB  
总提交次数:   AC次数:   平均分:
将本题分享到:
   
 
问题描述
  这是个复杂的世界。人类社会,自然界,还有地球之外的银河……
  ……
  每一天日出日落,人来人往,步履匆匆。究竟是为什么呢?那支配着一切的至高无上的法则又是否存在呢?Theresa知道,这个问题并不是一朝一夕就可以解答的,只有在仔细、深入的观察和思考以后,才有可能将所有支离破碎的线索联系起来,从而隐约窥见真实的答案。
  ……
  于是,Theresa经常思考生活中遇到的大大小小的问题。为什么港台出版的书籍里印刷的汉字她一个也不认识呢?为什么隔夜的白开水中富含一氧化二氢呢?为什么每年都有一段时间Gmail邮箱上不去呢?
  ……
  为了更加系统、科学地分析这些问题,Theresa决定向你求助。
  ……
  长话短说,Theresa想请你帮助她实现一个数据结构。这个数据结构的功能是在空间直角坐标系中维护一个点的集合,并支持以下三类操作:
  ……
  1. ADD x y z 加入一个新的点,点的坐标为(x, y, z)。
  2. QUERY x y z r 查询在正方体(x, y, z) - (x+r, y+r, z+r)内部的点的数目。
  3. CANCEL 撤销最近的一次ADD操作。
  ……
  其中x, y, z, r均为给出的整数。QUERY操作中,(x, y, z)为正方体的一个顶点的坐标,r为正方体的边长。在正方体边界上的点也算在正方体内部
  ……
  这个问题可能过于困难,所以Theresa并不强迫你实现一个高效的数据结构。然而,你必须对每一次QUERY操作给出正确的答案。
输入格式
  第一行包含一个整数N,表示最初的点集有N个点。
  接下来N行,每行包含三个整数xiyizi,依次表示每个点的坐标。
  第N+2行包含一个整数Q,表示将有Q次操作。
  接下来Q行,每行表示一次操作,格式如题目描述。
输出格式
  输出若干行,每行一个整数,依次表示每次查询操作的答案。
样例输入
2
1 2 3
1 1 3
7
ADD 0 4 3
QUERY 0 0 0 4
ADD 1 1 5
QUERY 1 1 2 3
QUERY 0 2 2 1
CANCEL
QUERY 1 1 2 3
样例输出
3
3
1
2
样例说明
  第1次查询正方体(0, 0, 0) - (4, 4, 4),内部包含点(1, 2, 3),(1, 1, 3),(0, 4, 3)。
  第2次查询正方体(1, 1, 2) - (4, 4, 5),内部包含点(1, 2, 3),(1, 1, 3),(1, 1, 5)。
  第3次查询正方体(0, 2, 2) - (1, 3, 3),内部包含点(1, 2, 3)。
  第4次查询正方体(1, 1, 2) - (4, 4, 5),内部包含点(1, 2, 3),(1, 1, 3)。
数据规模和约定
   对于10%的数据:1 N, Q 1 000
  此外10%的数据:0 x, y, z 1001 r 100
  此外30%的数据:没有ADD操作和CANCEL操作。
  此外20%的数据:没有CANCEL操作。
  以上70%的数据:1 N, Q 50 000
  对于100%的数据:1 ≤ N + Q ≤ 100 000 0 ≤ x, y, z, r ≤ 107r 为正整数。所有的CANCEL操作均为有效操作。不同的点的坐标可能重合。