算法分析: 如果用数组直接记录每一个区域的行星个数,在查询时需要O(n^3)的时间,速度较慢,所以可以采用树状数组来记录小行星的个数。这样只需要O((lg n)^3)的时间。大大提高了算法的效率。 根据题意还必须记录下每个返回的信息,以便纠错时使用。对于电话号码如果采用一个0..9999999的树组记录则浪费了很多的空间;如果依次记录每个电话号码,在查找时将浪费许多的时间。所以最好采用搜索树来存储每一个电话。
数据分析: 本题共有十个测试数据,分值从5~15不等,最大的数据有50万行命令。每个数据的询问,更新和纠错的个数比不尽相同,可以从多方面测试选手的程序。 参考程序: