【JZOJ 省选模拟】6638.Seat
题目
Description
Input
Output
共q行，每行一个整数，表示答案。
Sample Input
见下发文件
Sample Output
见下发文件
Data Constraint
对于所有数据，保证
有五个子任务
- (10pts)Mod<=1000,n<=100
- (20pts)Mod<=10^6
- (20pts)w<=10^5
- (30pts) n<=10^5
- (20pts) 没有特殊限制
思路
首先建出所有会出现的数字的trie
按照trie的深度从大到小对所有数字进行排序。
假设要对深度为w的这一层的节点进行排序（即这一层所有数字的长度为w），由于已经知道w+1层的节点排序的结果，由于x<=y --> [x/2]<=[y/2]，于是对上一层的所有节点替换成其父亲节点即可求出w层的排序结果。
特殊的，w层可能会出现trie中的叶子节点，将所有叶子节点直接排序，然后跟前面的归并即可。
这样就可以得到所有数字排序的结果。
时间复杂度O(n log Mod)