题意
有一个军队,每个人都有一个个性值,主角时不时会增加、或者移除一个指定个性值的战士,也可能试图添加一个指挥官。指挥官有两个属性,分别为个性值和领导力,如果一个现役战士的个性值与指挥官的个性值的异或小于领导力,那么这个战士会敬重该指挥官。
有n次操作,如果是试图添加指挥官的操作,要求输出现役战士中有多少人会敬重这位指挥官。
题解
个性值和领导力的取值范围都比较大,又有异或,比较明显地是在二进制上下功夫。像Trie树一样,对每位战士的个性值建树,每个节点是对应二进制位上的取值,最终到叶子节点的路径即可表示一个特定的个性值,在上面可以记录当前有几个战士具有这样的个性值。
如果没有异或这一回事,添加指挥官的时候只要逐位比较一遍即可,如果在第i位上指挥官的领导力为0,那么个性值为1的战士就不会敬重他,接着再比较个性值为0的战士里剩余的位;如果领导力为1,那么个性值为0的战士一定会敬重他,接着再比较个性值为1的战士里剩余的位。
有了异或之后,如果在第i位上指挥官的个性值为1,那么上述的判断条件就要倒过来,否则不用,就可以求出结果了。