lintcode 1695. Kanade的三重奏

给你一个数组A [1..n]，你需要计算多少三元组（i，j，k）满足（i <j <k）和（（A [i] xor A [j]）<（A [j] xor A [k]））

样例

样例 1:

输入：[1,2,3,4,5] 输出：6 解释：[1,2,4],[1,2,5],[1,3,4],[1,3,5],[2,3,4],[2,3,5]符合要求。

样例 2:

输入：[1,2,3] 输出：0 解释：[1,2,3]不符合要求。

注意事项

1≤n≤5∗10^5

0≤A[i]<2^30

输入测试数据 (每行一个参数)如何理解测试数据？

 

32位，计算2对xor操作得到的数，从哪一位开始不同的。对于计算每一位时，计算每一位上的每一个数时，只需计算它之前 和 之后 最后一位不同的对数（0——>1,1——>0）n0,n1。

public class Solution { /** * @param a: the array * @return: how many tuples in the array */ public long getCount(int[] a) { long cnt=0; int len=a.length; for(int k=31;k>=0;k--){//计算从哪一位开始不同的 HashMap<Integer,Long> pre=new HashMap<>(); HashMap<Integer,Long> post=new HashMap<>(); long n0=0,n1=0;//0-1对,1-0对 for(int i=1;i<len;i++){ int c=a[i]>>k; post.put(c,post.getOrDefault(c,0L)+1); } for(int i=1;i<len-1;i++){ int c1=a[i-1]>>k; int c2=a[i]>>k; if((c2&1)==0){//0,0,1 n1-=pre.getOrDefault(c2+1,0L); }else{ n0-=pre.getOrDefault(c2-1,0L); } pre.put(c1,pre.getOrDefault(c1,0L)+1); post.put(c2,post.getOrDefault(c2,0L)-1); if((c1&1)==0){//0-1对 n0+=post.getOrDefault(c1+1,0L); }else{ n1+=post.getOrDefault(c1-1,0L); } if((c2&1)==0){ cnt+=n0; }else{ cnt+=n1; } } } return cnt; } }