阿里云9.12后端笔试算法题解

1. 思维题。设x是n位数，令t=123456789100...00（n个0），此时可以构造x*y+z=t，其中z是t除以x的余数，则t-z的前10位必定为1234567890，因此答案为y=(t-z)/x。注意用long。复杂度O(lg(x))。

2. 前缀异或、动态规划。设xor(i)为数组前i个数异或的结果，则f(1)=xor(n), f(i)=f(i-1)^xor(i-1)^xor(n-i+1), i≥2。复杂度O(n)。

3. 线段树。在数组上用线段树维护二元组：(区间内最大值，区间内最大值的最小下标)。按照(购物时间->输入顺序)将所有顾客排序后依次询问：如果 区间的最大值-当前时间>0，输出对应的下标，然后将数组对应元素修改为-1并更新线段树；否则输出-1。复杂度O(m+n*log(m))。