SnackDown 2017 Online Elimination Round Prefix XOR

题目传送门

题意

给出$n$个数,定义上升为$a_i\leq a_i \quad xor \quad a_{i+1} \leq a_i \quad xor \quad a_{i+1} \quad xor \quad a_{i+2} \leq \dots \leq a_i \quad xor \quad a_{i+1} \quad xor \quad \dots \quad xor \quad a_{j}$,问每个区间的上升数对有多少?

思路

设$rig_i$表示以$i$为区间左端,使$(i,j)$满足上升的最大$j$。 设$sum_i$表示$xor$前缀和。 如果$a_r \quad xor \quad a_{r-1} \quad xor \quad \dots \quad xor \quad a_{i-1}>
a_{r+1} \quad xor \quad a_{r} \quad xor \quad \dots \quad xor \quad a_{i-1} $则不满足条件,那么$rig_i\leq r$。 即: 如果$sum_r \quad xor \quad sum_{i-1}> sum_{r+1} \quad xor \quad sum_{i-1} $则不满足条件,那么$rig_i\leq r$。 由于$xor$是位运算,所以考虑二进制下优化。 要满足条件,必须使$sum_r$与$sum_{r+1}$中至少有一位在二进制下不相同。 假设不相同的最高位是第$k$位,那么$sum_{i−1}$的第$k$位其实就有了限制,易得: (二进制下)
  1. $sum_r$的第$k$位为0,那么$sum_{i-1}$的第$k$位必须是1。
  2. $sum_r$的第$k$位为1,那么$sum_{i-1}$的第$k$位必须是0。
那么我们可以倒序枚举$i$,记录$S[j][0/1]$表示当前第$j$位限制为$0/1$时的位置,那样就可以快速求出$rig_i$了。 如果$[l,r]$不存在$rig_i>r$,那么答案显然就是$rig_i-i+1(l \leq i \leq r $且$ rig_i \leq r)$,但如果存在$rig_i>r$,由于不能越界,该部分的答案应该就是$r-i+1(l \leq i \leq r $且$ rig_i > r)$。由于强制在线,用主席树就可以解决了。

评论

  1. abc2237512422

    Orz

    7月前
    2019-2-26 21:49:17

发送评论


				
上一篇
下一篇