Submission #69682783

---

Source Code Expand

import java.io.*;
import java.util.*;

class TrieNode {
    TrieNode[] children = new TrieNode[2];
}

public class Main {
    static TrieNode root = new TrieNode();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        long m = Long.parseLong(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        Set<Integer> set = new TreeSet<>();
        
        for (int i = 0; i < n; i++) {
            set.add(Integer.parseInt(st.nextToken()));
        }
        
        for (int num : set) {
            insert(num);
        }
        
        System.out.println(calculateSum(0, m, 30));
        br.close();
    }
    
    static void insert(int num) {
        TrieNode curr = root;
        for (int i = 30; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (curr.children[bit] == null) {
                curr.children[bit] = new TrieNode();
            }
            curr = curr.children[bit];
        }
    }
    
    static int query(int x) {
        TrieNode curr = root;
        int result = 0;
        
        for (int i = 30; i >= 0; i--) {
            int bit = (x >> i) & 1;
            if (curr.children[bit] != null) {
                curr = curr.children[bit];
            } else {
                result |= (1 << i);
                curr = curr.children[1 - bit];
            }
        }
        return result;
    }
    
    static long calculateSum(long l, long r, int bit) {
        if (l >= r || bit < 0) return 0;
        
        if (r - l <= 100000) {
            long sum = 0;
            for (long x = l; x < r; x++) {
                sum += query((int)x);
            }
            return sum;
        }
        
        long mask = 1L << bit;
        long mid = ((l + mask - 1) / mask) * mask;
        
        if (mid >= r) {
            return calculateSum(l, r, bit - 1);
        }
        
        return calculateSum(l, mid, bit - 1) + calculateSum(mid, r, bit - 1);
    }
}

Submission Info

Judge Result