I don't know if the timeout restrictions have changed but my O(n) solution is passing without changing the boilerplate pretty quickly.

static List<Integer> freqQuery(List<List<Integer>> queries) {
    // one hash (numCtr) with key=>number, value=>occurances
    Map<Integer, Integer> numCtr = new HashMap<>();
    // one hash (occurancesCtr) with key=>occurances, value=>occurances of occurances
    Map<Integer, Integer> occurancesCtr = new HashMap<>();

    List<Integer> output = new LinkedList<>();

    for(List<Integer> query : queries) {
        final int currentCount = numCtr.getOrDefault(query.get(1), 0);
        if (query.get(0) == 1) {
            increaseByOne(numCtr, query.get(1));
            decreaseByOne(occurancesCtr, currentCount);
            increaseByOne(occurancesCtr, currentCount+1);
        } else if (query.get(0) == 2) {
            if (currentCount > 0) {
                decreaseByOne(numCtr, query.get(1));
                decreaseByOne(occurancesCtr, currentCount);
                if(currentCount-1 > 0) {
                    Solution.increaseByOne(occurancesCtr, currentCount-1);
                }
            }
        } else if (query.get(0) == 3) {
            if (occurancesCtr.getOrDefault(query.get(1), 0) > 0) {
                output.add(1);
            } else {
                output.add(0);
            }
        }
    }

static void decreaseByOne(Map<Integer, Integer> map, int key) {
    if(map.containsKey(key)) {
        map.put(key, map.get(key)-1);
    }
}

static void increaseByOne(Map<Integer, Integer> map, int key) {
    map.put(key, map.getOrDefault(key, 0)+1);
}
    return output;

}